[알고리즘] 선택정렬, 버블정렬, 삽입정렬, 퀵정렬

선택정렬 알고리즘.  [시간복잡도 O(n^2), 공간복잡도 O(n) ]

기준값을 기준으로 모든 내용을 검색하여 최저값을 찾아 기준값 위치에 대체한다. 

int a[] = {68, 9, 32, 2, 14, 7, 31, 26};
 
for( int i=0; i<a.length-1; i++){
    for(int j=i+1;j<a.length;j++){
        int min = i;
        // 오름차순을비교값을 반대로 넣어주면 된다. 
        if( a[j] > a[min] ){
            min = j;
        }
        
        //swap
        int temp = a[i];
        a[i] = a[min];
        a[min] = temp;
    }
    
    System.out.print(i+1 + "번째:");
    for(int v:a){
        System.out.printf("%3d", v);
    }
    System.out.println("");
}
 
/* result
1번째: 68  9 32  2 14  7 31 26
2번째: 68 32  9  2 14  7 31 26
3번째: 68 32 31  2  9  7 14 26
4번째: 68 32 31 26  2  7  9 14
5번째: 68 32 31 26 14  2  7  9
6번째: 68 32 31 26 14  9  2  7
7번째: 68 32 31 26 14  9  7  2
/*

버블정렬 알고리즘 [이미정렬되어있는경우O(n) 시간복잡도 O(n2), 공간복잡도 O(n) ]

좌우값을 비교해 나가면서 순서를 바꿔 정렬한다. 성능이 좋지 않으므로 사용하지 말자

int a[] = {68, 9, 32, 2, 14, 7, 31, 26};
 
for(int i=a.length-1;i>0;i--){
    System.out.println(a.length-i + "번째");
    for(int j=0;j<i;j++){
        if( a[j] < a[j+1]){
            int temp = a[j];
            a[j] = a[j+1];
            a[j+1] = temp;
        }
        for(int v:a){
            System.out.printf("%3d",v);
        }
        System.out.println("");
    }
}
/* result
1번째
 68  9 32  2 14  7 31 26
 68 32  9  2 14  7 31 26
 68 32  9  2 14  7 31 26
 68 32  9 14  2  7 31 26
 68 32  9 14  7  2 31 26
 68 32  9 14  7 31  2 26
 68 32  9 14  7 31 26  2
2번째
 68 32  9 14  7 31 26  2
 68 32  9 14  7 31 26  2
 68 32 14  9  7 31 26  2
 68 32 14  9  7 31 26  2
 68 32 14  9 31  7 26  2
 68 32 14  9 31 26  7  2
3번째
 68 32 14  9 31 26  7  2
 68 32 14  9 31 26  7  2
 68 32 14  9 31 26  7  2
 68 32 14 31  9 26  7  2
 68 32 14 31 26  9  7  2
4번째
 68 32 14 31 26  9  7  2
 68 32 14 31 26  9  7  2
 68 32 31 14 26  9  7  2
 68 32 31 26 14  9  7  2
5번째
 68 32 31 26 14  9  7  2
 68 32 31 26 14  9  7  2
 68 32 31 26 14  9  7  2
6번째
 68 32 31 26 14  9  7  2
 68 32 31 26 14  9  7  2
7번째
 68 32 31 26 14  9  7  2
/*

그런데 위에 처럼 하다보니 5번째 이후에는 변동이 없음에도 모두 검색을 하게 된다. 플래그를 둬서 변경이 없을경우에는 비교를 하지 않도록 변경해 보자. 아래는 변경된 소스이다. 

int a[] = {68, 9, 32, 2, 14, 7, 31, 26};
 
for(int i=a.length-1;i>0;i--){
    System.out.println(a.length-i + "번째");
    boolean changeFlag = false;
    for(int j=0;j<i;j++){
        if( a[j] < a[j+1]){
            int temp = a[j];
            a[j] = a[j+1];
            a[j+1] = temp;
            changeFlag = true;
        }
        for(int v:a){
            System.out.printf("%3d",v);
        }
        System.out.println("");
    }
    if( changeFlag == false ) break;
}
 
/* result
1번째
 68  9 32  2 14  7 31 26
 68 32  9  2 14  7 31 26
 68 32  9  2 14  7 31 26
 68 32  9 14  2  7 31 26
 68 32  9 14  7  2 31 26
 68 32  9 14  7 31  2 26
 68 32  9 14  7 31 26  2
2번째
 68 32  9 14  7 31 26  2
 68 32  9 14  7 31 26  2
 68 32 14  9  7 31 26  2
 68 32 14  9  7 31 26  2
 68 32 14  9 31  7 26  2
 68 32 14  9 31 26  7  2
3번째
 68 32 14  9 31 26  7  2
 68 32 14  9 31 26  7  2
 68 32 14  9 31 26  7  2
 68 32 14 31  9 26  7  2
 68 32 14 31 26  9  7  2
4번째
 68 32 14 31 26  9  7  2
 68 32 14 31 26  9  7  2
 68 32 31 14 26  9  7  2
 68 32 31 26 14  9  7  2
5번째
 68 32 31 26 14  9  7  2
 68 32 31 26 14  9  7  2
 68 32 31 26 14  9  7  2
/*

삽입정렬

2번째 기준값부터 좌측을 비교하여 삽입하는 방식이다. 

int a[] = {68, 9, 32, 2, 14, 7, 31, 26};
 
for (int i = 1; i < a.length; i++) {
    int key = a[i];
    int idx = i-1;
    System.out.print(i+"번째:");
    while(idx>=0 && key<a[idx]){
        a[idx+1] = a[idx];
        idx--;
    }
    a[idx+1] = key;
    for(int v:a){
        System.out.printf("%3d",v);
    }
    System.out.println("");
}
 
/* result
1번째
1번째:  9 68 32  2 14  7 31 26
2번째:  9 32 68  2 14  7 31 26
3번째:  2  9 32 68 14  7 31 26
4번째:  2  9 14 32 68  7 31 26
5번째:  2  7  9 14 32 68 31 26
6번째:  2  7  9 14 31 32 68 26
7번째:  2  7  9 14 26 31 32 68
/*

퀵정렬 [시간복잡도 O[nlogn] ~최악 O[n^2]

기준점을 잡고 기준보다 작은건 좌측으로 큰건 우측으로 보낸후 재귀함수를 이용하여 각각 다시 호출한다. 

public void sort(int[] data, int l, int r){
    int left = l;
    int right = r;
    int pivot = data[(l+r)/2];
    
    do{
        while(data[left] < pivot) left++;
        while(data[right] > pivot) right--;
        
        if(left <= right){    
            int temp = data[left];
            data[left] = data[right];
            data[right] = temp;
            left++;
            right--;
        }
        
        for(int v:data){
            System.out.printf("%3d",v);
        }
        System.out.println("");
        
    }while (left <= right);
    
    if(l < right) sort(data, l, right);
    if(r > left) sort(data, left, r);
}
 
public static void main(String[] args) {
    
    int data[] = {66, 10, 1, 20, 34, 5, -10};
    
    for(int v:data){
        System.out.printf("%3d",v);
    }
    System.out.println("");
    
    Test1 quick = new Test1();
    quick.sort(data, 0, data.length - 1);
    
    for(int v:data){
        System.out.printf("%3d",v);
    }
}
 
/* result 
 66 10  1 20 34  5-10
-10 10  1 20 34  5 66
-10 10  1  5 34 20 66
-10 10  1  5 34 20 66
-10  5  1 10 34 20 66
-10  5  1 10 34 20 66
-10  1  5 10 34 20 66
-10  1  5 10 34 20 66
-10  1  5 10 20 34 66
-10  1  5 10 20 34 66
-10  1  5 10 20 34 66
*/

Arrays api를 이용하여 배열 정렬하는 법

int data[] = {66, 10, 1, 20, 34, 5, -10};
Arrays.sort(data);
for(int v:data){
    System.out.printf("%3d",v);
}
// result
// -10  1  5 10 20 34 66

내부적으로 quicksort를 사용하고 있어, 위에 것과 별반 차이가 없음.