2022. 10. 25. 00:21ㆍIntelligence Technology
정렬은
무작위로 섞여있는 자료들을 오름차순 또는 내림차순으로 정리를 하는 작업을 의미합니다.
코딩을 하시다 보면 sorting은 정말 자주 쓰이는 문법인데 method()로 적용이 가능합니다.
그래도 어떤 원리로 작동을 하는지 아시면 상황에 맞는 코딩을 통해 더욱 효율적인 작업이 가능하실 겁니다.
우선 sorting을 하시기 전에 현재 데이터들이 어떤 상태인지를 아셔야 합니다.
1. 데이터의 양
2. 어떤 상태로 배열이 되어 있는지
3. 작업시간 및 소요공간
데이터들이 수억 개가 넘어가면 sorting의 종류에 따라서도 응답 시간이 많이 달라집니다.
그럼 각각의 정렬에는 어떤 분류 방법들이 있는지 알아보겠습니다.
1. 삽입 정렬(Insertion Sort)
삽입 정렬은 가장 간단한 구조의 정렬 방법입니다. 첫 번째 데이터와 두 번째 데이터를 비교하고 정렬이 필요하면 실행. 그다음은 세 번째 데이터를 첫 번째, 두 번째 데이터와 비교 후 정렬이 필요하면 작업을 합니다.
아래의 예시를 통해 확인해 보겠습니다.
초기 상태는 7 5 6 2 4입니다
1회전은 2번째 값과 첫 번째 값을 비교한 뒤 5를 첫 번째 자리에 삽입하고 7을 한 칸 뒤로 이동시킵니다.
2회전에서는 6과 5를 비교 후 지나가고 7과 6을 비교 후 교체한 뒤 7을 한 칸 뒤로 이동시킵니다.
3회전에서는 2와 5를 비교 후 교체를 해준 뒤 나머지를 한 칸씩 뒤로 이동시킵니다.
4회전에서는 4와 2를 비교 후 지나가고 5와 비교 후 교체를 해주면 완성이 됩니다.
2. 선택 정렬(Selection Sort)
선택 정렬은 N개의 데이터에서 최솟값을 찾아 첫 번째 열로 이동시키고 나머지 N-1개 중에서 다시 최솟값을 찾아 다음 열로 옮기는 작업을 반복하는 정렬 방법입니다. 각 순번들을 보시면 처음에는 N-1번의 검색을 통한 작업을 진행하고 2회전 때는 N-2번의 작업 식으로 매 순번마다 검색 및 작업을 하는 횟수가 줄어듭니다.
3. 버블 정렬(Bubble Sort)
버블 정렬을 인접한 열끼리 값을 비교하여 크기에 따라 정렬을 하는 방식입니다. 앞 뒤로 계속 비교를 하며 순번이 지날수록 제일 앞에 위치한 값들만 비교를 하게 됩니다.
4. 퀵 정렬(Quick Sort)
정렬 방식중에서 가장 빠른 방식입니다. 하나의 값을 기준(Pivot)으로 삼고 배열을 균등한 크기로 분할합니다. 분할된 배열을 정렬 후 다시 피벗을 기준으로 합치면 됩니다. Pivot은 제일 왼쪽, 오른쪽 또는 가운데 중에서 임의로 선택을 하면 됩니다.
위와 같이 Pivot을 기준으로 계속 비교하면서 완료가 되면 피벗과 중간 값을 교체해 줍니다. 그리고 배열의 크기가 0이나 1이 된다면 Quick 정렬이 완료가 되게 됩니다. 단, 프로그램에서 다시 불러오기를 해야 되기에 스택(Stack)이 필요한 정렬입니다.
5. 합병 정렬(Merge Sort)
이미 정렬이 되어 있는 두 개의 데이터를 하나로 합친 후 정렬할 때 사용합니다.
정렬 방법은 두개의 키들을 한 쌍으로 묶은 뒤 각 쌍에 대해 순서를 정합니다. 그 후 순서대로 정렬된 각각의 쌍들을 하나씩 더 합쳐서 크기를 키워준 뒤 다시 정렬을 합니다. 위와 같이 반복하다 보면 더 이상 쌍으로 나뉘지 않고 하나로 합쳐지는데 그때 마지막으로 정렬을 해주면 종료가 되는 방식입니다.
예를 들면
그룹1: 33, 65, 46, 28, 24 / 그룹 2: 99, 76, 35, 12, 30로 분리되어 있는데 합병 정렬을 해보겠습니다.
1회전: (33, 99), (65, 76), (46, 35), (28, 12), (24, 30)
2회전: (33, 99), (65, 76), (35, 46), (12, 28), (24, 30)
위와 같이 순서대로 배열을 해줍니다.
3회전: (33, 99, 65, 76), (35, 46, 12, 28), (24, 30)
위와 같이 묶인 묶음을 2개씩 다시 묶어 크기를 키워줍니다.
4회전: (33, 65, 76, 99), (12, 28, 35, 46), (24, 30)
묶은 쌍에서 다시 정렬을 진행합니다.
5회전: (33, 65, 76, 99, 12, 28, 35, 46), (24, 30)
크기를 한번 더 키워줍니다.
6회전: (12, 28, 33, 35, 46, 65, 76, 99), (24, 30)
묶은 쌍에서 다시 정렬을 진행합니다.
7회전: (12, 28, 33, 35, 46, 65, 76, 99, 24, 30)
크기를 한번 더 키워줍니다.
8회전: (12, 24, 28, 30, 33, 35, 46, 65, 76, 99)
묶은 쌍에서 다시 정렬을 진행합니다.
위와 같은 방법으로 합병 정렬은 진행이 됩니다.
이상으로 정렬(sort)의 개념과 종류에 대해 알아보는 포스팅을 마치겠습니다.
오늘도 똑구의 꿀팁 블로그를 방문해 주셔서 감사합니다.
'Intelligence Technology' 카테고리의 다른 글
| [운영체제] 운영체제 정의, 인터페이스, 작업 처리 방법 (0) | 2022.12.04 |
|---|---|
| [운영체제] 시스템 소프트웨어 개념 및 구성 (0) | 2022.11.16 |
| [데이터베이션] 자료구조 이진 트리 및 이진 탐색 트리 (0) | 2022.10.23 |
| [데이터베이스] 자료구조 - 트리(Tree)의 개념(비선형 구조) (0) | 2022.10.23 |
| [데이터베이스] 자료구조 - 스택(Stack), 큐(Queue), 데크(Deque)의 개념 및 처리 방법 비교 (0) | 2022.10.22 |