정렬 알고리즘

1. 버블정렬 

// int[] arr를 정렬한다고 가정

for(int i=0; i<arr.length-1;i++){
	for(int j=0; j<arr.length-1-i;j++){
    	if(arr[j] > arr[j+1]){
        	int temp = arr[j]
            arr[j] = arr[j+1]
            arr[j+1] = temp;
        }
    }
}

정렬하려는 자료 수가 N개라면, 빅오는 N^2이다.

 

2. 선택정렬

// int[] arr 정렬한다고 가정

for(int i=0; i<arr.length-1;i++){
	int Idx = i;
    
    for(int j = i+1; j<arr.length;j++){
    	if(arr[Idx] > arr[j])
        	Idx = j;
    }
	int temp = arr[i];
    arr[i] = arr[idx];
    arr[idx] = temp;

}

정렬하려는 자료 수가 N개라면, 빅오는 N^2이다.

 

3. 삽입정렬

//int[] arr을 정렬한다고 가정
int i,j;
for( i=1; i<arr.length;i++){
	 int target = arr[i];
     for( j= i-1; j>=0;j--){
     	if(target < arr[j]){
        	arr[j+1] = arr[j];
        }else break;
     }
     arr[j+1] = target;
}

정렬하려는 자료 수가 N개라면, 빅오는 N^2이다.

 

4. 힙정렬

//일단 힙이 필요함..

public class Heap{
	int num;
    int[] arr;
    Comparator<Integer> com;
	
    public Heap(Comparator<Integer> com){
    this.com = com;
    arr= new int[100];
    num = 0;
    }
    
    public int getParent(int idx){
    return idx/2;
    }
    
    public int getLeftChild(int idx){
    return idx*2;
    }
    
    public int getRightChild(int idx){
    return getLeftChild(idx)+1;
    }
    
    public int getHiPriorityChildIdx(int idx){
    	if(getLeftChild(idx) > num) return 0;
       	if(getLeftChild(idx) == num) return getLeftchild(idx);
    	
        if(com.compare(arr[getLeftChild(idx),arr[getRightChild(idx)] < 0 ){
        	return getRightChild(idx);
        }else{
        	return getLeftChild(idx);
        }
    }
    
    public void InsertData (int data){
    	int dataIdx = num+1;
        
        while(dataIdx != 1){
        	if(com.compare(data,arr[getParent(dataIdx)]) > 0 ){
            	arr[dataIdx] = arr[getParent(dataIdx)];
                dataIdx = getParent(dataIdx);
            }else break;
        }
    	arr[dataIdx] = data;
        num++;
    }
    
    public int delete(){
    	int Dedata = arr[1];
        int lastData = arr[num];
        int DataIdx = 1;
        int child;
        
        while(true){
        	child = getHipriorityChildIdx(DataIdx);
            if(child == 0 && com.compare(lastData,arr[child]) >= 0)
             break;
             
             arr[DataIdx] = arr[child];
             DataIdx = child;
        }
        arr[DataIdx] = lastData;
        num--;
        return Dedata;
    }
}

//int[] arr을 정렬한다고 할때
Heap h = new Heap((a,b) -> {
	return a-b;
})
for(int i=0; i<arr.length;i++){
	h.InsertData(arr[i]);
}
for(int i=0; i<arr.length;i++){
	arr[i] = h.delete();
}

힙만 구현한다면, 힙에다가 자료를 넣다가 빼면 된다.

nlog2N의 시간복잡도를 가진다.

 

5. 합병정렬

 

//int[] arr을 정렬한다고 가정

mergeSort(int[] arr, int left, int right){
	int mid;
	if(left < right){
    	
        mid = (left+right)/2;
        
        mergeSort(arr, left, mid);
        mergeSort(arr, mid+1, right);
    	mergeSum(arr,mid,left,right);
    
    }
}

mergeSum(int[] arr, int mid, int left, int right){

	int startLeft = left;
    int startRight = mid+1;
    int newIdx = left;
    int[] sortArr = new int[right+1];
    
    while(startLeft <= mid && startRight <= right){
    
        if(arr[startLeft] > arr[startRight]){
    		sortArr[newIdx] = arr[startRight++];     
        }else{
        	sortArr[newIdx] = arr[startLeft++];
        }
    }
    
    if(startLeft > mid){
    	for(int i=startRight; i<=right; i++){
        	sortArr[newIdx++] = arr[i];
        }
    }else{
    	for(int i= startLeft; i<=mid ; i++){
        	sortArr[newIdx++] = arr[i];
        }
    }
    
    for(int i=left;i<=right;i++){
    	arr[i] = sortArr[i];
    }

}

 재귀적으로 정렬하는 합병정렬이다. 자료의 갯수가 N일때 빅오는 Nlog2N이다.

 

6. 퀵 정렬

 

//int[] arr을 정렬한다고 가정

void quickSort(int[] arr, int left, int right){

	if(left<=right){
    	
        int pivot = getPart(arr,left,right);
        quickSort(arr,left,pivot-1);
        quickSort(arr,pivot+1;right);
    	
    }

}

int getPart(int[] arr, int left, int right){

	int pivotValue= arr[left];
    
  	int low = left;
    int high = right;
    
    while(low <= high){
    
    	while(low <= right && pivotValue >= arr[low]) //low == right+1은 out
        	low++;
        while(right>=(left-1) && pivotValue <= arr[high]) // right == left는 out
            high--;
    	
        if(low <= high)
          swap(arr,low,high);
    }
    swap(arr,left,high);
    

	return high;
}

void swap (int[] arr, int idx1, int idx2){
	int temp = arr[idx1];
    arr[idx1] = arr[idx2];
    arr[idx2] = temp;
}

 

자료가 N개일 때 퀵정렬의 성능은 Nlog2N이다.