정렬 그림으로 개념정리(버블정렬, 교환정렬, 삽입정렬, 선택정렬, 쉘정렬, 힙정렬, 퀵정렬, 기수 정렬) - 자료구조, 컴퓨터 알고리즘

정렬(Sorting)? 

- 리스트나 기록의 요소를 재배열 하는 것 .. 오름차순, 내림차순으로 정렬한다

- 정렬시에는 primary key, secondary key 를 이용하기도 함

 

왜인지 모르지만 정렬과 탐색은 항상 같이 배운다

 

** 아래의 예시들은 모두 왼→오 오름차순 정렬

 

1. 버블 정렬( Bubble Sort) = 교환 정렬( Exchange Sort)

이름 답게 하나씩 비교하면서 정렬을 하는 방식이다.

list[0]과list[1]과 비교 : list[1]이 크면 둘이 바꾸기

→ list[1]과 list[2] 비교 : list[2]가 크면 둘이 바꾸기

... continue 

 

이걸 시작점~ 끝까지 한번 하는게 한 번의 수행

 

Best case(정렬이 이미 되어있는 상황)

: 정렬을 할 필요가 없으니까 비교연산만 n-1 번 => Θ(n)

 

 

Worst case(거꾸로 정렬되어있는 상황)

매번 비교연산을 n-1, n-2, n-3번 ... 해야하므로 => Θ(n^2)

 

Initialize n = Length of Array
BubbleSort(Array, n)
{
    for i = 0 to n-2
    {
        for j = 0 to n-2
        {
            if Array[j] > Array[j+1]
            {
                swap(Array[j], Array[j+1])
            }
        }
    }
}

 

2. 선택 정렬 (Selection Sort)

 

위의 예시를 참고하면 되는데 list에서 가장 큰 값(cmax)를 찾고 해당 값과 리스트의 마지막 값을 교환

(리스트의 마지막에 있던 요소는 원래 cmax의 위치로 가게 됨)

-> 한 번의 수행을 통해 하나의 요소가 정렬됨

다음 수행에서는 정렬 안된 요소(첫 cmax를 제외한 값들) 중 max값을 찾아서 cmax를 초기화

...continue

 

* 시간 복잡도

이 정렬의 경우 best case, worst case, average time complexity 모두 같다.

정렬 여부와 상관없이 비교를 반복하기 때문!

 

* 선택정렬 psuedo code

procedure selection sort 
   list  : array of items
   n     : size of list

   for i = 1 to n - 1
   /* set current element as minimum*/
      min = i    
  
      /* check the element to be minimum */

      for j = i+1 to n 
         if list[j] < list[min] then
            min = j;
         end if
      end for

      /* swap the minimum element with the current element*/
      if indexMin != i  then
         swap list[min] and list[i]
      end if
   end for
	
end procedure

 

3. 삽입 정렬(Insertion Sort)

정렬된 부분 // 정렬 안된 부분으로 나누어서 정렬하는 방식

앞(왼쪽)에서 부터 정렬 후 정렬 안된 부분의 요소를 순차적으로 정렬된 부분의 올바른 위치에 삽입한다

 

* 삽입 정렬 psuedo code

---

 

 

 

procedure insertionSort( A : array of items )
   int holePosition
   int valueToInsert
	
   for i = 1 to length(A) inclusive do:
	
      /* select value to be inserted */
      valueToInsert = A[i]
      holePosition = i
      
      /*locate hole position for the element to be inserted */
		
      while holePosition > 0 and A[holePosition-1] > valueToInsert do:
         A[holePosition] = A[holePosition-1]
         holePosition = holePosition -1
      end while
		
      /* insert the number at hole position */
      A[holePosition] = valueToInsert
      
   end for
	
end procedure

 

 

---

4. 쉘 정렬(Shell Sort)

 

요소들을 요소가 t개인 부분리스트로 나누어 각 리스트의 k번째 끼리 정렬하는 방식

Shell 정렬의 장점:

 - 각 비교연산에 대해 inversion이 없으므로 시간복잡도가 Θ(n^2) 보다 좋을 것

---

 

 

 

procedure shellSort()
   A : array of items 
	
   /* calculate interval*/
   while interval < A.length /3 do:
      interval = interval * 3 + 1	    
   end while
   
   while interval > 0 do:

      for outer = interval; outer < A.length; outer ++ do:
	   
     
      /* select value to be inserted */
      valueToInsert = A[outer]
      inner = outer;
		 /삽입 정렬을 이용해 inner 번째 요소들 정렬/
         /*shift element towards right*/
         while inner > interval -1 && A[inner - interval] >= valueToInsert do:
            A[inner] = A[inner - interval]
            inner = inner - interval
         end while

      /* insert the number at hole position */
      A[inner] = valueToInsert

      end for

   /* calculate interval*/
   interval = (interval -1) /3;	  

   end while
   
end procedure

---

 

 

 

5. 퀵 정렬(Quick Sort)

퀵 정렬은 특이하게 pivot값을 이용한다.

pivot 이란?

1. (회전하는 물체의 균형을 잡아 주는) 중심점[축] 2. (가장 중요한) 중심[중심축] 

(출처: 네이버 영어사전)

설정한 pivot값을 기준으로

 

이 과정을 반복한다.

pivot값을 어떻게 설정하느냐의 방식으로는 2가지가 있는데

1) 가장 왼쪽 or 오른쪽 or 가운데 등 특정 위치를 기준으로 설정

2) 매 수행마다 리스트 내의 random 한 값을 기준으로 설정

 

 

* 퀵 정렬 psuedo code

<재귀적 방법>

---

 

 

function partitionFunc(left, right, pivot)
   leftPointer = left
   rightPointer = right - 1

   while True do
      while A[++leftPointer] < pivot do
         //do-nothing            
      end while
		
      while rightPointer > 0 && A[--rightPointer] > pivot do
         //do-nothing         
      end while
		
      if leftPointer >= rightPointer
         break
      else                
         swap leftPointer,rightPointer
      end if
		
   end while 
	
   swap leftPointer,right
   return leftPointer
	
end function

 

 

procedure quickSort(left, right)

   if right-left <= 0
      return
   else     
      pivot = A[right]
      partition = partitionFunc(left, right, pivot)
      quickSort(left,partition-1)
      quickSort(partition+1,right)    
   end if		
   
end procedure

---

 

 

6. 힙 정렬(Heap Sort)

 

힙정렬을 수행하려면 maxheap, minheap에 대한 개념이 필요하다.

간단하게 말하면 max heap의 각 노드는 자신의 자식 노드보다 값이 크거나 같은 완전 이진트리 이다.

 

힙 정렬의 과정

1. heap 만들기

2. heap 정렬하기 

 

더 구체적으로 살펴보면

1. max heap을 만든다(Heapify) => 그럼 root에 제시된 요소들 중 max값이 존재

2. root와 heap의 마지막 요소를 swap

3. 기존의 root값( 즉, heap의 마지막 요소) 를 제외하고 heap을 재구성(Heapify)

4. 2,3의 과정을 반복한다.

 

해당 예시를 살펴보면 모든 노드는 각자의 자식 노드보다 크다 (maxheap이 이미 구성되어 있는 상태)

이제 위의 2,3 과정을 반복하는 것이다.

 

* 힙 정렬 psuedo code

---

 

 

Heapify(A as array, n as int, i as int)
{
    max = i
    leftchild = 2i + 1
    rightchild = 2i + 2
    if (leftchild <= n) and (A[i] < A[leftchild])
        max = leftchild
    else 
        max = i
    if (rightchild <= n) and (A[max]  > A[rightchild])
        max = rightchild
    if (max != i)
        swap(A[i], A[max])
        Heapify(A, n, max)
}
Heapsort(A as array) 
{
   n = length(A)
   for i = n/2 downto 1   
     Heapify(A, n ,i)
   
   for i = n downto 2
     exchange A[1] with A[i]
     A.heapsize = A.heapsize - 1
     Heapify(A, i, 0)
}

---

 

7. 기수 정렬 (Radix sort) 

 

이 정렬 방식에는 조건이 2개 있다.

   1. 정렬하고자 하는 key 값들은 모두 음수가 아닌 정수로 진수가 통일되어 있어야 한다.
   2. 모든 key 값은 같은 자리수여야 한다.

이 정렬 방식은 그냥 그림으로 보는게 쉽다

얘를 들어 3자리 수면 

모든 key 값을 100의자리 "숫자" 기준으로 정렬

=> 10의 자리 "숫자" 기준으로 정렬

=> 1의 자리 "숫자" 기준으로 정렬

끝 이다.

 

 

* 기수 정렬 psuedo code

 

---

 

 

void radixsort{
	for (i=1; i<=numdigits; i++){
    	distribute(i);
        coalesce;
        }
    }
}

void distribute( index l){
	for(j=0; j<=9;j++)
   	 list[j]=NULL;
   	p= masterlist;
    while(p!=NULL){
    	j=value of ith digit in p->key;
        q=p;
        p=p->link
        link q to the end of list[j];
    }
}

void coalesce(){
	index j;
    masterlist=NULL;
    for (j=0;j<=9;j++)
    	link the node in list[j] to the end of masterlist
}
        

 

 

 

 

 

 

 

 

 

참고자료

이화여대 이상호 교수님 컴퓨터 알고리즘 수업자료

fullyunderstood.com/pseudocodes/heap-sort/

www.tutorialspoint.com/data_structures_algorithms/quick_sort_algorithm.htm

www.tutorialspoint.com/data_structures_algorithms/shell_sort_algorithm.htm

fullyunderstood.com/pseudocodes/bubble-sort/

www.tutorialspoint.com/data_structures_algorithms/selection_sort_algorithm.htm

www.tutorialspoint.com/data_structures_algorithms/insertion_sort_algorithm.htm

www.geeksforgeeks.org/radix-sort/

Radix Sort - GeeksforGeeks