📌 데이터 입, 출력 구현 - 정렬(Sort)

 

 

목차

 

삽입 정렬 (Insertion Sort)

📌 삽입 정렬은 가장 간단한 정렬 방식으로 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬한다.

 

• 두 번째 키와 첫 번째 키를 비교해 순서대로 나열(1회전)하고, 이어서 세 번째 키를 첫 번째, 두 번째 키와 비교해 순서대로 나열(2회전)하고, 계속해서 n번째 키를 앞의 n-1개의 키와 비교하여 알맞은 순서에 삽입하여 정렬하는 방식이다.
• 평균과 최악 모두 수행 시간 복잡도는 0(n2승) 이다.
• 시간 복잡도의 가장 간단한 정의는 알고리즘의 성능을 설명하는 것이다. 다른 의미로는 알고리즘을 수행하기 위해 프로세스가 수행해야 하는 연산을 수치화 한 것이. 왜 실행시간이 아닌 연산수치로 판별할까? 명령어의 실행 시간은 컴퓨터의 하드웨어 또는 프로그래밍 언어에 따라 편차가 크게 달라 지기 때문에 명령어의 실행 횟수만을 고려하는 것이다.

 

O(1) > O(logN) > O(N) > O(NlogN) > O(N2승) > O(2N승) > O(N!)

 

• 삽입 정렬의 장단점
  • 최선의 경우 O(N)이라는 엄청나게 빠른 효율성을 가지고 있다.
  • 성능이 좋아서 다른 정렬 알고리즘의 일부로 사용될 만큰 좋은 정렬법이다.
  • 최악의 경우 0(n2승) 이라는 시간 복잡도를 갖게 되며, 데이터의 크기, 종류에 따라 실행 편차가 크다.

 

🔔 예) 8, 5, 6, 2, 4를 삽입 정렬로 정렬하시오

초기 상태 : 8, 5, 6, 2, 4

1회전 : 8, 5, 6, 2, 4 / 5, 8, 6, 2, 4

두 번째 값을 첫 번째 값과 비교하여 5를 첫 번째 자리에 삽입하고 8을 한 칸 뒤로 이동시킨다.

2회전 : 5, 8, 6, 2, 4 / 5, 6, 8, 2, 4

세 번째 값을 첫 번째, 두 번째 값과 비교하여 6, 8 자리에 삽입하고 8은 한 칸 뒤로 이동시킨다.

3회전 : 5, 6, 8, 2, 4 / 2, 5, 6, 8, 4

네 번째 값 2를 처음부터 비교하여 맨 처음에 삽입하고 나머지를 한 칸씩 뒤로 이동시킨다.

4회전 : 2, 5, 6, 8, 4 / 2, 4, 5, 6, 8

다섯 번째 값 4를 처음부터 비교하여 5자리에 삽입하고 나머지를 한 칸씩 뒤로 이동시킨다.

 

 

쉘 정렬 (Shell Sort)

📌 쉘 정렬은 삽입 정렬(Insertion Sort)을 확장한 개념이다.

 

• 입력 파일을 어떤 매개변수(b)의 값으로 서브 파일을 구성하고, 각 서브 파일을 Insertion 정렬 방식 으로 순서 배열하는 과정을 반복하는 정렬 방식(h = 3루트n), 즉 임의의 레코드 키와 h값 만큼 떨어진 곳의 레코드 키를 비교하여 순서화되어 있지 않으면 서로 교환하는 것을 반복하는 정렬 방식이다.
• 입력 파일이 부분적으로 정렬되어 있는 경우에 유리한 방식이다.
• 평균 수행 시간 복잡도는 0(n1.5승) 이고, 최악의 수행 복잡도는 0(n2승)이다.
• 쉘 정렬의 장단점
  • 삽입 정렬의 단점을 보완해서 만든 정렬법으로 삽입 정렬도 성능이 뛰어난 편이지만 더 뛰어난 성능을 갖는 정렬법이다
  • 일정한 간격에 따라서 배열을 바라봐야 한다. 즉 이 '간격'을 잘못 설정한다면 성능이 굉장히 안좋아질 수 있다.

 

선택 정렬 (Selection Sort)

📌 선택 정렬은 n개의 레코드 중에서 최소값을 찾아 첫 번째 레코드 위치에 놓고, 나머지 (n-1)개 중에서  다시 최소값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬하는 방식이다.

 

• 평균과 최악 모두 수행 시간복잡도는 0(n2승)로써 그리 썩 좋은 알고리즘은 아니다.

 

🔔 예제) 8, 5, 6,2, 4 를 선택 정렬로 정렬하시오.

 

• 선택 정렬의 장단점
  • 선택 정렬은 또한 버블 정렬과 마찬가지로 구현이 쉬운 편에 속하는 정렬법이다.
  • 정렬을 위한 비교 횟수는 많지만 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료 상태에서 효율적으로 사용될 수 있다.

 

 

버블 정렬 (Bubble sort)

• 버블 정렬은 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식이다.
• 평균과 최악 모두 수행 시간 복잡도는 0(n2승)로써 그리 썩 좋은 알고리즘은 아니다.

 

🔔 예제) 8, 5, 6, 2, 4를 버블 정렬로 정렬하시오.

 

• 버블 정렬의 장단점
  • 구현이 쉽다. Bubble정렬은 인접한 값만 계속해서 비교하면 되는 방식으로 굉장히 구현이 쉬운 편이다. 코드 자체가 직관적이다.
  • 굉장히 비효율적이다. 최악이든 최선이든 0(n2승)이라는 시간복잡도를 갖기 때문에 사실 알고리즘에서 효율적인 정렬방법으로 사용되지는 않는다.

 

 

퀵 정렬 (Quick sort)

📌 퀵 정렬은 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬하는 방법으로 키를 기준으로 작은 값은 왼쪽에, 큰 값은 오른쪽 서브 파일로 분해시키는 방식으로 정렬한다.

 

• 위치에 관계 없이 임의의 키를 분할 원소로 사용할 수 있다.
• 정렬 방식 중에서 가장 빠른 방식이다.
• 프로그램에서 되부름을 이용하기 때문에 스택(Stack)이 필요하다.
• 분할(Divide)과 정복(Conquer)을 통해 자료를 정렬한다.
  • 분할(Divide) : 기준 값인 피봇(Pivot)을 중심으로 정렬할 자료들을 2개의 부분 집합으로 나눈다.
  • 정복(Conquer) : 부분 집합의 원소들 중 피봇(Pivot)보다 작은 원소들은 왼쪽, 피봇(Pivot)보다 큰 원소들은 오른쪽 부분 집합으로 정렬한다.
  • 부분 집합의 크기가 더 이상 나누어질 수 없을 때까지 분할과 정복을 반복 수행한다.
• 퀵 정렬의 장단점
  • 기준 값에 의한 분할을 통해서 구현하는 정렬법으로써, 분할 과정에서 logN 이라는 시간이 걸리게 되고 전체적으로 보게 되면 NlogN 으로써 실행시간이 빠른 편이다.
  • 기준값(Pivot)에 따라서 시간 복잡도가 크게 달라진다.

 

힙 정렬 (Heap Sort)

📌 힙 정렬은 전이진(완전 이진) 트리(Complete Binary Tree)를 이용한 정렬 방식이다.

 

• 구성된 전이진 트리를 Heap Tree로 변환하여 정렬한다.
• 전이진 트리란 각 노드가 최대 2개의 자식 노드를 갖는 트리 형태의 자료구조로서 마지막 레벨을 제외한 모든 노드는 완전히 채워져 있어야 한다. 또한, 최 하단 레벨의 노드는 좌측만 노드가 채워져 있거나 좌측과 우측 모두 채워져 있어야 한다.

 

• 힙 정렬의 장단범
  • 추가적인 메모리를 필요로 하지 않으면서 항상 0(NlogN)이라는 시간복잡도를 가지는 괸장히 정렬법들 중에서 효율적인 정렬법이라고 볼 수 있다. 퀵 정렬도 효율적이라고 볼 수 있지만 최악의 경우 시간이 오래 걸린다는 단점이 있지만 힙 정렬의 경우 항상 0(NlogN)으로 보장된다는 장점이 있다.
  • 데이터의 상태에 따라서 다른 정렬법들에 비해서 조금 느린 편이다. 또한, 안정성(Stable)을 보장 받지 못한다는 단점이 있다.

🔔 예) 17, 14, 13, 15, 16, 19, 11, 18, 12를 Heap 트리로 구성하시오.

 

1. 주어진 파일의 레코드들을 전이진 트리로 구성한다.

 

2. 전이진 트리의 노드의 역순으로 자식 노드와 부모 노드를 비교하여 큰 값을 위로 올린다.

3. 교환된 노드들을 다시 검토하여 위의 과정을 반복한다.

 

 

2-Way 합병 정렬 (Merge Sort)

📌 2-Way Merge Sort는 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식이다.

그 방법은 다음과 같다.

 

• 두 개의 키들을 한 쌍으로 하여 각 쌍에 대하여 순서를 정한다.
• 순서대로 정렬된 각 쌍의 키들을 합병하여 하나의 정렬된 서브리스트로 만든다.
• 위 과정에서 정렬된 서브리스트들을 하나의 정렬된 파일이 될 때까지 반복한다.
• 평균과 최악 모두 시간복잡도는 0(NlogN)이다.

 

🔔 예) 71, 2, 38, 5, 7, 61, 11, 26, 53, 42를 2-Way 합병 정렬로 정렬하시오.

• 1회전 : 두 개씩 묶은 후 각각의 묶음 안에서 정렬한다.

(71, 2) (38, 5) (7, 61) (11, 26) (53, 42)

(2, 71) (5, 38) (7, 61) (11, 26) (42, 53)

• 2회전 : 묶여진 묶음을 두 개씩 묶은 후 각각의 묶음 안에서 정렬한다.

((2, 71) (5, 38)) ((7, 61) (11, 26)) (42, 53)

(2, 5, 38, 71) (7, 11, 26, 61) (42, 53)

 

🔔 예) 71, 2, 38, 5, 7, 61, 11, 26, 53, 42를 2-Way 합병 정렬로 정렬하시오.

• 3회전 : 묶여진 묶음을 두 개씩 묶은 후 각각의 묶음 안에서 정렬한다.

((2, 5, 38, 71) (7, 11, 26, 61)) (42, 53)

(2, 5, 38, 71) (7, 11, 26, 61)) (42, 53)

• 4회전 : 묶여진 묶음 두 개를 하나로 묶은 후 정렬한다.

((2, 5, 7, 11, 26, 38, 61, 71) (42, 53))

2, 5, 7, 11, 26, 38, 42, 53, 61, 71

 

• 2-Way 합병 정렬의 장단점
  • 퀵 정렬과 비슷하게 원본 배열을 반씩 분할해 가면서 정렬하는 정렬법으로써 분할 하는 과정에서 logN 만큼의 시간이 걸린다. 즉, 최종적으로 보게 되면 NlogN이 된다. 퀵 정렬과 달리, Pivot을 설정하거나 그런 과정 없이 무조건 절반으로 분할하기 때문에 Pivot에 따라서 성능이 안좋아지거나 하는 경우가 없다. 따라서 항상 0(NlogN) 이라는 시간 복잡도를 갖게 된다.
  • 장점만 본다면 퀵 정렬보다는 무조건 병합 정렬을 사용하는 것이 좋다고 생각할 수 있지만 가장 큰 단점은 '추가적인 메모리 필요'이다. 병합정렬은 임시배열에 원본 맵을 계속해서 옮겨주면서 정렬을 하는 방법이기 때문이다.

 

 

기수 정렬 (Radix Sort) = Bucket Sort

📌 정렬되지 않은 자료를 버킷이라는 단위 기억 장소에 여러 그룹으로 정렬하고 버킷별 키 값에 따라 다시 정렬하는 알고리즘이다.

 

• 정렬법들 중에서 0(N) 이라는 말도 안 되는 시간 복작도를 갖는 정렬법으로써 일단 엄청나게 빠르다.
• 정렬법에서 0(NlogN)을 깰 수 있는 방법은 없다고 알려져 있는데, 그 방법을 깨는 유일한 방법이 기수 정렬법이다.
• '버킷' 이라는 추가적인 메모리가 할당되어야 한다. 즉, 메모리가 업청나게 여유롭다면 상관이 없겠지만 메모리가 생각보다 많이 소비되는 정렬법이다.
• 데이터 타입이 일정한 경우에만 가능하다. 기존에 정렬법들은 음수와 양수, 실수와 정수가 섞여 있더라도 비교를 하려면 할 수 있었지만, 기수 정렬의 경우 양의 정수는 양의 정수끼리만, 음의 정수는 음의 정수끼리만 정렬이 가능하다.
• 즉, 엄청나게 빠른 대신에 구현을 위한 조건이 굉장히 많이 붙기 때문에 그렇게 많이 사용되는 방법은 아니다.

 

Sorting	장점	단점
버블 정렬	구현이 쉽다.	시간이 오래 걸리고 비효율적이다.
선택 정렬	구현이 쉽다. 비교하는 횟수에 비해 교환이 적에 일어난다.	시간이 오래 걸려서 비효율적이다.
퀵 정렬	실행시간 0(NlogN)으로 빠른 편이다.	Pivot에 의해서 성능의 차이가 심하다. 최악의 경우 O(N2승)이 걸리게 된다.
힙 정렬	항상 0(NlogN)으로 빠른 편이다.	추가적인 메모리 공간을 필요로 한다.
삽입 정렬	최선의 경우 0(N)으로 굉장히 빠른 편이다. 성능이 좋아서 다른 정렬법에 일부로 사용됨.	최악의 경우  0(N2승)으로, 데이터의 상태에 따라서 성능 차이가 심하다.
쉘 정렬	삽입정렬보다 더 빠른 정렬법이다.	설정하는 '간격'에 따라서 성능 차이가 심하다.
기수 정렬	0(N)이라는 말도 안 되는 속도를 갖는다.	추가적인 메모리가 '많이' 필요하다. 데이터 타입이 일정해야 한다. 구현을 위한 조건이 많이 붙는다.