[자료구조]CH9. 정렬(정렬의 이해~퀵 정렬)

참조: C로 배우는 쉬운 자료구조(이지영 저)

공부 날짜 : 21.03.17

 

<Section1> 정렬의 이해

 

1. 정렬의 개념

 

정렬(sort)이란 순서 없이 배열된 자료를 작은 것부터 큰 것 순서인 오름차순(Ascending)이나 큰 것부터 작은 것 순서인 내림차순(Descending)으로 재배열하는 것이다.

 

자료를 정렬하는 데 사용하는 기준이 되는 특정값을 키라고 한다. 

 

2. 정렬 방식의 분류

 

 1) 내부 정렬 : 정렬할 자료를 메인 메모리에 올려서 정렬하는 방식

  속도는 빠르지만 정렬할 수 있는 자료의 양이 메인 메모리의 용량에 따라 제한된다.

구분	종류	비고
비교식	교환방식	선택 정렬, 버블 정렬, 퀵 정렬
	삽입방식	삽입 정렬, 셀 정렬
	병합방식	2-way 병합, n-way 병합
	선택방식	(이진트리를 사용)히프 정렬, 트리 정렬
분배식	분배방식	기수 정렬

 2) 외부 정렬 : 보조기억장치를 사용

 속도는 떨어지지만, 보조기억 장치를 대용량으로 쓸 수 있어 내부정렬로 처리할 수 없는 대용량 자료를 정렬할 수 있다.

 

<Section2> 선택 정렬

 

1. 선택 정렬의 이해(Selection Sort)

 

 전체 원소 중에서 기준 위치에 맞는 원소를 선택해 자리를 교환하는 방식으로 정렬한다.

전체 원소 중에서 가장 작은 원소를 찾은 다음 첫째 원소와 자리를 교환한다. 그 다음 둘째로 작은 원소를 찾고 둘째 원소와 자리를 교환하고, 이를 반복하면서 정렬을 완성한다.

 

2. 선택 정렬 알고리즘

크기가 n인 배열 a[]의 원소를 선택 정렬

 

 selectionSort(a[],n)

     for (i ← 0 ; i < n ; i ← i+1) do {

         a[i] , ... , a[n-1] 중에서 가장 작은 원소 a[k]를 선택해 a[i]와 교환한다.

     }

 end selectionSort()

 

 선택 정렬에서의 공간복잡도는 n이고, 시간복잡도는 O(n^2)이다.

 

<Section3> 버블 정렬

 

1. 버블 정렬의 이해(Bubble Sort)

 

 인접한 원소를 두 개 비교하여 자리를 교환하는 방식을 반복하여 정렬한다. 

버블 정렬을 수행하면 인접한 처음 두 개 원소부터 인접한 마지막 원소까지 비교하는 작업과 자리를 교환하는 작업을 반복하면서 가장 큰 원소가 마지막에 정렬된다. 

 

2. 버블 정렬 알고리즘

크기가 n인 배열 a[]의 원소를 버블 정렬

 

 bubbleSort(a[] , n)

    for (i ← n-1 ; i >= 0 ; i ← i-1) do { //마지막 자리에 가장 큰 수부터 정렬되므로 크기는 점점 작아짐

        for (j ← 0 ; j < i ; j ← j+1) do { //첫 번째 인덱스부터 배열되지 않은 인덱스까지 인접 원소 비교

            if (a[j] > a[j+1]) then { //인접 원소 비교

                temp ← a[j];

                a[j] ← a[j+1];

                a[j+1] ← temp; //만약 앞의 원소 값이 크다면 자리를 교환

            }

        }

    }

 end bubbleSort()

 

 <Section4> 퀵 정렬

 

1. 퀵 정렬의 이해(Quick Sort)

 

 기준값을 중심으로 왼쪽 부분집합과 오른쪽 부분집합으로 분할(Divide)한다. 

왼쪽 부분집합에는 기준값보다 작은 원소를 이동시키고, 오른쪽 부분집합에는 기준값보다 큰 원소를 이동시킨다. 

이때, 기준값을 피봇(pivot)이라고 한다. 

 

 1) 왼쪽 끝에서 오른쪽으로 움직이면서 크기를 비교하여 피봇보다 크거나 같은 원소를 찾아 L로 표시한다. 

  단, L은 R과 만나면 더 이상 오른쪽으로 이동하지 못하고 멈춘다. 

 

 2) 오른쪽 끝에서 왼쪽으로 움직이면서 피봇보다 작은 원소를 찾아 R로 표시한다. 

  단, R은 L과 만나면 더 이상 왼쪽으로 이동하지 못하고 멈춘다.

 

 3-1) 1),2)에서 찾은 L원소와 R원소가 있는 경우, 서로 교환하고 L과 R의 현재 위치에서 1)과 2)의 작업을 반복한다. 

 

 3-2) 1),2)를 진행하다가 L과 R이 같은 원소에서 만나 멈춘 경우, 피봇과 R의 원소를 교환한다.

  교환한 위치를 피봇 자리로 확정하고 현재 단계의 퀵 정렬을 끝낸다. 

 

 4) 피봇의 확정된 위치를 기준으로 만들어진 새로운 왼쪽 부분집합과 오른쪽 부분집합에 대해서

  1)~3)의 퀵 정렬을 순환적으로 반복 수행하는데, 모든 부분집합의 크기가 1이하가 되면 전체 퀵 정렬을 종료한다.

 

2. 퀵 정렬 알고리즘

 

*크기가 n인 배열 a[]의 원소를 퀵 정렬

 

 quickSort(a[] , begin , end)

     if (m < n) then { //begin<end

        p ← partition(a , begin , end); // 피봇 설정

        quickSort(a[] , begin , p-1); //왼쪽 부분 퀵 정렬

        quickSort(a[] , p+1 , end); //오른쪽 부분 퀵 정렬

     }

 end quickSort()

 

*배열 a[]를 두 개로 분할하는 partition()연산

 

 partition(a[],begin,end)

     pivot ← (begin + end)/2; //중간값을 피봇으로 정함

     L ← begin; //시작값

     R ← end; //끝값

     while (L < R) do {

         while (a[L] < a[pivot] and J < R) do L++; //L이 피봇보다 크거나 같은 수를 찾을 때까지 오른쪽으로 이동

         while (a[R] >= a[pivot] and J < R) do R--; //R이 피봇보다 작은 수를 찾을 때까지 왼쪽으로 이동

         if (L < R) then { //L과 R을 찾았는데 둘의 값이 만나지 않았을 때

             temp ←a[L];

             a[L]←a[R];

             a[R]←temp; //L과 R의 값을 교환

         }

     }

     // L과 R이 만났을 때

     temp ←a[pivot];

     a[pivot]←a[R];

     a[R]←temp; //L과 R이 만난 원소와 피봇을 교환

     return R; //교환된 피봇의 자리를 반환

 end partition()