[Sort] Bubble Sort, Selection Sort, Insertion Sort (C언어)

코딩테스트 문제 풀다가 정렬에 대해 정리해본다.

 

참고로 C언어로 작성한다.

 

 

1. 버블 정렬

2. 선택 정렬

3. 삽입 정렬

 

 

성능은 버블, 선택, 삽입 세 가지  다 동일하다.

 

시간복잡도 O(n²)

 

---

 

 

1. 버블 정렬

 : 매 반복마다 가장 큰 값이 뒤로 이동

 

// 버블 정렬 (Bubble Sort)

void bubbleSort(int array[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

 

 

array[]

: 정렬할 배열

n

: 배열 길이

for (int i = 0; i < n - 1; i++)

 : 전체 정렬 반복 횟수

 : 배열 길이가 n이면 최대 n-1번 반복

for (int j = 0; j < n - 1 - i; j++)

 : 인접한 값 비교용 반복문

 : 뒤쪽은 이미 정렬되므로 - i 로 비교 범위를 줄인다.

  1회전 -> 전체 비교

  2회전 -> 마지막 값 정렬 완료 -> 하나 줄어듦

if (array[j] > array[j + 1])

 : 왼쪽 값이 더 크면

int temp = array[j];

 : 값 교환을 위한 임시 변수

array[j] = array[j + 1];

 : 오른쪽 값을 왼쪽으로 이동

array[j + 1] = temp;

 : 원래 왼쪽 값을 오른쪽으로 이동

 

 

버블 정렬은 한 바퀴 돌 때마다 가장 큰 값이 맨 뒤로 가기 때문에

for문 조건이 j<n-1- i ;  로  i를 빼준다.

 

---

 

 

2. 선택 정렬

 : 매 반복마다 가장 작은 값을 앞으로 이동

 

// 선택 정렬 (Selection Sort)

void selectionSort(int array[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;

        for (int j = i + 1; j < n; j++) {
            if (array[j] < array[minIndex]) {
                minIndex = j;
            }
        }

        int temp = array[i];
        array[i] = array[minIndex];
        array[minIndex] = temp;
    }
}

 

 

void selectionSort(int array[], int n)

 : 배열과 길이 전달

for (int i = 0; i < n - 1; i++)

 : 정렬 위치를 하나씩 확정 ( [정렬됨] [정렬 안됨] )

int minIndex = i;

 : 현재 위치를 최소값 후보로 설정

for (int j = i + 1; j < n; j++)

 : 뒤쪽에서 더 작은 값 찾기

if (array[j] < array[minIndex])

 : 더 작은 값 발견

minIndex = j;

 : 최소값 위치 갱신

int temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;

 : 최소값을 현재 위치화 교환

 

i 조건이 n-1인 이유는

만약 i < n 으로 하게될 경우

마지막 반복인 i = n-1 에서

for( int j = n; j<n; j++) 과 같기 때문에 조건 실패로 아무 작업도 하지 않는다.

의미가 없기 때문에 n-1 로 지정하는 것.

 

---

 

 

3. 삽입 정렬

 : 값을 적절한 위치에 끼워 넣음

 

 

// 삽입 정렬 (Insertion Sort)

void insertionSort(int array[], int n) {
    for (int i = 1; i < n; i++) {
        int key = array[i];
        int j = i - 1;

        while (j >= 0 && array[j] > key) {
            array[j + 1] = array[j];
            j--;
        }

        array[j + 1] = key;
    }
}

 

 

for (int i = 1; i < n; i++)

 : 두 번째 원소부터 시작

int key = array[i];

 : 현재 삽입할 값 저장

int j = i - 1;

 : key 앞쪽에서 비교 시작

while (j >= 0 && array[j] > key)

array[j + 1] = array[j];

 : 왼쪽 값이 key 보다 크면 오른쪽으로 한 칸 이동

j--;

 : 한 칸 더 왼쪽으로 이동하여 계속 비교

array[j + 1] = key;

 : key를 알맞은 위치에 삽입

 

 

두 번째 값을 key로 두고 첫 번째 값이랑 비교해서

만약 key보다 비교할 값이 큰 경우 비교할 값을 다음 자리로 보내고

key에 담아놓은 값을 앞자리에 대입한다.

인덱스0 까지 (key의 앞에 있는 모든 숫자들) 비교해야하므로 j--; 하고 

조건은 j >= 0 이다. 

반복.