[정렬]간단히 정리하는 선택, 버블, 삽입 정렬

1. Selection Sort

1) 개념

각 루프마다 

- 최대의 원소를 찾는다. 

- 최대의 원소와 맨 오른쪽 원소를 교환한다. 

- 맨 오른쪽 원소를 제외한다. 

하나의 원소만 남을 때 까지 위의 루프를 반복한다.

[출처: 권오흠, 영리한 프로그래밍을 위한 알고리즘 강좌]

2) Pseudocode

selectionSort(A[ ], n){   ▷배열 A[1...n]을 정렬한다.

for last ← n downto  2 {        -------------------------------①

A[1...last] 중 가장 큰 수 A[k]를 찾는다     -----------------------②

A[k] ↔ A[last]  ▷ A[k]와 A[last]의 값을 교환    -------------------------③

}

}

3) 수행시간

①의 for 루프는 n-1번 반복

②에서 가장 큰 수를 찾기 위한 비교횟수: n-1, n-2, ..., 2, 1

③의 교환은 상수시간 작업

4) 시간복잡도

5) 내가 짠 코드

#include<stdio.h>
 
int main(void){
    int i,j,min,index, temp;
    int array[10] = {1,10,5,8,7,6,4,3,2,9};
    
    for(i=0;i<10;i++){
        min = 99999;
        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. Bubble Sort

1) 개념

두 인접한 원소를 검사하여 정렬하는 방법이다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다.

다른 숫자와 비교하여 제일 큰 수를 뒤로 보내는 작업은 Selection Sort와 비슷하다.

2) Pseudocode

bubbleSort(A[ ], n) { ▷배열 A[1...n]을 정렬한다.

for last ← n downto  2 {        -------------------------------①

for i ← 1 to last-1    -----------------------②

if(A[i]>A[i+1]) then A[i] ↔ A[i+1]  ▷ 교환 -------------------------③

}

}

3) 수행시간

①의 for 루프는 n-1번 반복

②의 for 루프는 각각 n-1, n-2, ..., 2, 1번 반복

③의 교환은 상수시간 작업

4) 시간복잡도

5) 내가 짠 코드

//옆에 있는 값과 비교해서 더 작은 값을 앞으로 보내면 어떨까? 
//비교해주는 집합을 줄여줌으로서 구해진다. 
#include<stdio.h>
 
int main(){
    int i,j, temp;
    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;
            }
        }
        
    }
    for(i=0;i<10;i++){
        printf("%d ",array[i]);
    }
    return 0;
} 

3. Insertion Sort (삽입 정렬)

1) 개념

자료 배열의 모든 요소를 앞에서 부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

2) Pseudocode

insertionSort(A[ ], n){ ▷배열 A[1...n]을 정렬한다.

for i ← 1 to { -------------------------------① 

A[1...i]의 적당한 자리에 A[i]를 삽입한다. -------------------②

}

}

3) 수행시간

①의 for 루프는 n-1번 반복

②의 삽입은 최악의 경우 i-1번 비교

4) 시간복잡도 - 최악의 경우

5) 내가 짠 코드

//항상 왼쪽은 정렬이 되어 있기 때문에 
// 멈출곳을 알고 있기 때문에 더 효율적인 코드다. 
#include<stdio.h>
 
int main(){
    int i,j, temp;
    int array[10] = {1,10,5,8,7,6,4,3,2,9};
    
    for(i=0;i<9;i++){
        j=i; // 현재의 원소를 선택해서 적절한 위치에 넣는다.
        while(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;
}