[정보처리기사] 여러 종류의 정렬(Sort)에 대해 알아보자

 

 안녕하세요. 진득코딩입니다. 프로그래밍을 꿈꾸는 사람들에게 가장 무난하고 보편적인 자격증은 정보처리기사 자격증이라고 생각합니다.

 

 이번 시간에는 정보처리기사의 시험 범위에 포함되어 있는 정렬(Sort)에 대해 알아보고 어떤 종류의 정렬이 있는지 알아보도록 하겠습니다.

 

 정렬의 정의

 

 프로그래밍을 하다 보면 데이터를 다루어야 할 일이 많이 생기게 됩니다.

 

 특히 AI의 중요성이 더더욱 커지는 현 시점에서 데이터에 대한 중요도는 점점 더 커지고 다루어야 할 데이터들은 점점 더 양이 방대해지고 있습니다.

 

 정렬은 데이터를 원활하게 검색하게 해줍니다.

 

 사람은 수십에서 수백 개 정도의 데이터만 다루지만 컴퓨터가 다루어야 할 데이터는 보통 백만 개 단위이며 데이터베이스의 경우에는 이론상 무한 개의 데이터를 다룰 수 있어야 합니다.

 

 탐색할 대상 데이터가 정렬되어 있지 않다면 순차 탐색 외에는 다른 알고리즘을 사용할 수 없지만 데이터가 정렬되어 있다면 이진 탐색이라는 강력한 알고리즘을 사용할 수 있게 됩니다.

 

 이렇게 정렬을 하는데 여러 방법이 있습니다. 각각의 정렬에 대해서 알아보도록 하겠습니다.

 

삽입 정렬(Insertion Sort)

 

• 삽입 정렬은 가장 간단한 정렬 방식으로, 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬하는 방식입니다.
  
  
• 평균과 최악 모두 수행 시간 복잡도는 O(n^2)입니다.
  
  
  

7

3

5

1

 

 위와 같이 4개의 숫자를 예시로 들도록 하겠습니다.

 

 앞에서부터 각 자리에 있는 숫자보다 앞에 있는 숫자들과 비교하여 알맞은 자리로 들어가도록 하면 됩니다.

 

 가장 앞에 있는 7이라는 숫자는 앞에 숫자가 없기 때문에 두 번째 자리에 있는 3을 기준으로 생각하면 됩니다.

 

 3을 기준으로 앞에 있는 숫자인 7와 비교하면 3이 더 작기 때문에 3이 첫 번째 자리로 가게 되고 7을 한 칸 뒤로 이동시킵니다.

 

이렇게 하면 삽입 정렬의 1회전이 완료된 것입니다.

 

3

7

5

1

 

 이번에는 세번째 자리에 있는 5를 기준으로 생각하겠습니다.

 

 앞에 있는 숫자들인 3과 7을 비교하면 3보다는 크지만 7보다는 작기 때문에 5는 두 번째 자리에 삽입되고 7은 뒤로 한 칸 밀려나게 됩니다.

 

3

5

7

1

 

 마지막으로 네 번째 자리에 있는 1이라는 숫자를 기준으로 생각해 보겠습니다.

 

 1을 기준으로 앞에 있는 숫자들을 처음부터 비교하게 되면 이미 3보다 작은 숫자이기 때문에 1이 첫 번째 자리에 들어가게 되고 3은 뒤로 한 칸 밀려나게 됩니다.

 

1

3

5

7

 

 이렇게 총 3회전 만에 정렬이 완료되었습니다.

 

 위와 같이 맨 앞에 있는 자리에 있는 숫자를 기준으로 그 숫자보다 앞에 있는 숫자들과 비교하여 자기 자리를 찾아가는 정렬이라고 생각하시면 됩니다.

 

선택 정렬(Selection Sort)

 

• 선택 정렬은 n개의 레코드 중에서 최솟값을 찾아 첫 번째 레코드 위치에 놓고, 나머지 (n-1)개 중에서 다시 최소값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬하는 방식입니다.
  
  
• 평균과 최악 모두 수행 시간 복잡도는 O(n^2)입니다.
  
  

• 1회전
  
  

7

3

5

1

 

 위와 똑같은 숫자들을 기준으로 예시를 들어보도록 하겠습니다. 

 선택 정렬은 1회전에서는 첫 번째 자리를 선택하고 해당 자리와 다른 자리들을 비교해서 정렬하게 됩니다.

 

3

7

5

1

 

 맨 앞자리에 있는 숫자 7과 두 번째 자리에 있는 숫자 3을 비교했을 때 7이 더 크기 때문에 이 둘의 자리를 바꾸게 됩니다.

 

3

7

5

1

 

 이번에는 첫 번째 자리와 세 번째 자리를 비교하게 됩니다.

 

 3보다 5가 더 크기 때문에 위치를 바꾸지 않습니다.

 

1

7

5

3

 

 마지막으로 첫 번째 자리와 네 번째 자리를 비교하게 됩니다.

 

 3보다 1이 더 작기 때문에 위치를 바꾸게 됩니다.

 

 이렇게 되면 1회전이 완료된 것입니다.

 

• 2회전

 

1

7

5

3

 

 2회전은 두 번째 자리에 있는 숫자인 7을 뒤에 있는 숫자들과 비교하면 됩니다.

 

 앞에 있는 자리와 비교하지 않는 이유는 1회전이 끝나면 첫 번째 자리에 있는 숫자는 이미 정렬된 상태이기 때문입니다.

 

7과 5를 비교하게 되면 숫자 5가 더 작기 때문에 자리를 바꿔줍니다.

 

1

5

7

3

 

 2회전의 주인공인 두 번째 자리에 있는 5와 4번째 자리에 있는 3과 숫자를 비교하게 됩니다.

 

 숫자 3이 더 작기 때문에 자리를 바꿔줍니다.

 

1

3

7

5

 

 이렇게 마지막에 있는 4번째 자리까지 모두 비교하게 되면 1회전이 더 완료되어 총 2회전이 완료된 상태가 되었습니다.

 

• 3회전
  
  

1

3

7

5

 

이번에는 세 번째 자리를 기준으로 비교하면 됩니다.

 

 세 번째 자리에 있는 7을 기준으로 네 번째 자리에 있는 숫자 5와 비교하게 되면 숫자 5가 더 작기 때문에 자리를 바꿔줍니다.

 

1

3

5

7

 

 네 번째 자리는 더 이상 비교할 숫자가 없기 때문에 더 이상 정렬할 필요가 없습니다.

 

 이렇게 3회전 만에 선택 정렬을 완료하게 되었습니다.

 

버블 정렬(Bubble Sort)

 

• 버블 정렬은 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식입니다.
  
  
• 평균과 최악 모두 수행 시간 복잡도는 O(n^2)입니다.

• 1회전

7

3

5

1

 

 위에서 사용한 예시로 버블 정렬에 대해서 살펴보도록 하겠습니다.

 

 버블 정렬은 맨 앞에 있는 숫자를 기준으로 바로 뒤에 있는 숫자와 계속해서 자리를 바꿔주시면 됩니다.

 

 가장 먼저 첫 번째 자리에 있는 7과 두 번째 자리에 있는 3을 비교했을 때 3이 더 작기 때문에 자리를 바꿔주게 됩니다.

 

3

7

5

1

 

 두 번째 자리에 있는 7과 그 바로 뒤에 있는 숫자인 5를 비교하게 되면 5가 더 작기 때문에 자리를 바꿔주시면 됩니다.

 

3

5

7

1

 

 세 번째 자리에 있는 7과 바로 뒤에 있는 숫자인 1을 비교하게 되면 1이 더 작기 때문에 자리를 바꿔주게 됩니다.

 

3

5

1

7

 

 이제 네 번째 자리의 차례이지만 뒤에 있는 숫자가 없기 때문에 1회전이 완료되었습니다.

 

• 2회전
  
  
  

3

5

1

7

 

 첫 번째 자리에 있는 3을 기준으로 5와 비교했을 때 5가 더 크기 때문에 자리를 바꾸지 않습니다.

 

3

5

1

7

 

 두 번째 자리에 있는 5를 기준으로 바로 뒤에 있는 숫자인 1과 비교하게 되면 1이 더 작기 때문에 자리를 바꿔주게 됩니다.

 

3

1

5

7

 

 버블 정렬에서는 1회전을 마친 상태라면 뒤에서부터 1자리가, 2회전을 마친 상태라면 뒤에서부터 2자리가 정렬이 완료된 상태가 됩니다.

앞에서부터 정렬이 완료되는 선택 정렬과 상반되는 성질이라고 볼 수 있습니다.

 

 세 번째 자리에 있는 5를 기준으로 뒤에 있는 숫자 중에서 정렬되지 않은 숫자가 없기 때문에 2회전이 완료되었습니다.

 

• 3회전
  
  

3

1

5

7

 

 위에서처럼 첫 번째 자리에 있는 숫자 3과 바로 뒤에 있는 숫자 1을 비교하면 1이 더 작기 때문에 자리를 바꿔줍니다.

 

1

3

5

7

 

 두 번째 자리 기준으로 뒤에 정렬이 되지 않은 숫자가 없기 때문에 3회전이 완료되었습니다.

 

 또한 4회전을 하게 되면 첫 번째 자리를 기준으로 정렬하게 되는데 첫 번째 자리를 기준으로 뒤에 정렬이 되지 않은 숫자가 없기 때문에 버블 정렬이 완료되었습니다.

 

쉘 정렬(Shell Sort)

 

• 쉘 정렬부터는 실제로 하는 방법이나 몇 회전했을 때의 몇 번째 숫자가 오는지 등에 대한 직접적으로 계산해야 하는 문제는 나오지 않기 때문에 개념적으로 알고 있으면 됩니다.
  
  
• 쉘 정렬은 입력 파일을 어떤 매개 변수의 값으로 서브 파일을 구성하고, 각 서브 파일을 Insertion 정렬 방식으로 순서 배열하는 과정을 반복하는 정렬 방식입니다.
  
  
• 쉘 정렬은 삽입 정렬(Insertion Sort)을 확장한 개념입니다.
  
  
• 평균 수행 시간 복잡도는 O(n^1.5)이고, 최악의 수행 시간 복잡도는 O(n^2)입니다.
  
  

퀵 정렬(Quick Sort)

 

•  퀵 정렬은 키를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽 서브 파일에 분해시키는 과정을 반복하는 정렬 방식입니다.
  
  
• 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬합니다.
  
  
• 평균 수행 시간 복잡도는 O(log₂n)이고, 최악의 수행 시간 복잡도는 O(n^2)입니다.
  
  

힙 정렬(Heap Sort)

 

• 힙 정렬은 전이지 트리를 이용한 정렬 방식입니다.
  
  
• 구성된 전이진 트리(Complete Binary Tree)를 Heap Tree로 변환하여 정렬합니다.
  
  
• 평균과 최악 모두 시간 복잡도는 O(nlog₂n)입니다.
  
  

2-Way 합병 정렬(Merge Sort)

 

• 2-Way 합병 정렬은 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식입니다.
  
  
• 평균과 최악 모두 시간 복잡도는 O(nlog₂n)입니다.
  
  

기수 정렬(Radix Sort / Bucket Sort)

 

• 기수 정렬은 Queue를 이용하여 자릿수(Digit) 별로 정렬하는 방식입니다.
  
  
• 레코드의 키 값을 분석하여 같은 수 또는 같은 문자끼리 그 순서에 맞는 버킷에 분배하였다가 버킷의 순서대로 레코드를 꺼내어 정렬합니다.
  
  
• 평균과 최악 모두 시간 복잡도는 O(dn)입니다.
  
  

---

 

 이번 시간에는 정렬에 대해서 알아보았습니다.

 정렬은 알고리즘에서도 중요한 개념이니 머릿속에 잘 정리하는 것이 좋다고 생각합니다.

 

 이번 포스팅은 여기까지입니다.

 끝까지 봐주셔서 감사합니다.😊