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

1. 선택 정렬  ( O(n^2) )

: 배열을 차례대로 탐색하며 탐색하는 항 우측의 항 중 최솟값을 찾아서 위치 변경.

int i=0;j=0,min=0,index=0,temp=0;
int array[10]={1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
for(i=0;i<10;i++){
    min=9999;
    for(j=i;j<10;j++){
        if(min>array[j]){
            min=array[j];
            index=j;
        }
    }
    temp=array[i];
    array[i]=array[index];
    array[index]=temp;
}
for(i=0;i<10;i++){
    printf("%d ", array[i]);
}
return 0;

 

 

 

2. 버블 정렬 ( O(n^2) )

: 차례대로 두 항씩 비교하며 좌측 항이 크면 자리 변경을 반복. 최댓값이 차례대로 우측에 쌓이는 형태!

int i=0,j=0,temp=0;
int array[10]={1,10,5,8,7,6,4,3,2,9};
for(i=0;i=10;i++){
    for(j=0;j<9-i;j++){
        if(array[j]>array[j+1]){
            temp=array[j];
            array[j]=array[j+1];
            array[j+1]=temp;
        }
    }
}

 

 

3. 삽입 정렬  ( O(n^2) )

: 데이터가 이미 거의 정렬된 상태이면 어떤 알고리즘보다 빠르다는 특징을 가짐.

  범위를 점차 넓혀가며 왼쪽으로 최솟값을 모는 형태. (1씩 증가하는 key(i)의 좌측에 있는 항을 정렬)

int i=0,j=0,temp=0;
int array[10]={1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
for(i=0;i<10;i++){
    j=i;
    while(j>=0 && array[j]>array[j+1]){
        temp=array[j];
        array[j]=array[j+1];
        array[j+1]=temp;
        j--;
    }
}
for(i=0;i<10;i++){
    printf("%d ",array[i]);
}
return 0;

 

 

4. 퀵 정렬(분할 정복 알고리즘 중 하나) ( O(n*logn) )

: 특정한 값(피벗, 보통 첫 번째 원소)을 기준으로 큰 숫자와 작은 숫자를 서로교환한 뒤에 배열을 반으로 나눔.

  C++에서 제공해주는 <algorithm> 라이브러리의 sort()함수를 이용하면 편함.(최악의 경우에서도 O(n*logn)을 보장. 클릭

예시 : {5,3,10,8,1,4,9,2,6,7} key값에 밑줄! 1-1 : {5,3,2,8,1,4,9,10,6,7} 1-2 : {5,3,2,4,1,8,9,10,6,7} 1-3 : {1,3,2,4,'5',8,9,10,6,7} 엇갈림! j와 키값 교체 좌측 파티션 2-1 : {'1',2,3,4,'5',8,9,10,6,7} i=1, j=0 엇갈림. 나머지도 보나마나 차례대로 정렬됨 2-2 : {'1','2',3,4,'5',8,9,10,6,7} 2-3 : {'1','2','3',4,'5',8,9,10,6,7} 2-4 : {'1','2','3','4','5',8,9,10,6,7} 우측 파티션 3-1-1 : {'1','2','3','4','5',8,7,10,6,9} 3-1-2 : {'1','2','3','4','5',8,7,6,10,9} 3-1-3 : {'1','2','3','4','5',6,7,'8',10,9} 엇갈림. 3-2-1 : {'1','2','3','4','5','6','7','8',10,9} 엇갈림. 3-3-1 : {'1','2','3','4','5','6','7','8','9','10'} i=10, j=9 엇갈림.

void quickSort(int *data, int start, int end){
    int temp=0;
    //원소가 1개인 경우
    if(start>=end){
        return;
    }
    int key=start;  //key는 첫 번째 원소.
    int i=start+1;  //순방향으로 key보다 큰 값 찾기.
    int j=end;      //역방향으로 key보다 작은 값 찾기.
    
    while(i<=j){    //탐색하다가 i와 j가 엇갈릴 때 까지 반복.
        //내림차순으로 변경하고 싶을 때는 아래 와일문의 부등호를 반대로 바꿔주면 됨.
        
        //키 값보다 큰 값을 만날 때까지 오른쪽으로 이동.
        while(data[i]<=data[key]){
            i++;
        }
        //키 값보다 작은 값을 만날 때까지 왼쪽으로 이동.(단 범위 엇나감 방지를 위해 조건 추가)
        while(data[j]>=data[key] && j>start){
            j--;
        }
        
        //엇갈린 상태이면 j와 키 값 교체.
        if(i>j){
            temp=data[j];
            data[j]=data[key];
            data[key]=temp;
        }else{ //엇갈리지 않았으면 찾은 i와 j 교체.
            temp=data[j];
            data[j]=data[i];
            data[i]=temp;
        }
    }
    quickSort(data,start,j-1); //왼쪽 파티션
    quickSort(data, j+1, end); //오른쪽 파티션
}