[4] 정렬과 검색
정렬과 검색은 알고리즘이 쓰이는 대표적인 처리입니다.
이번에는 어떤 정렬방법과 검색 방법이 있는지 알아보겠습니다.
정렬
정렬
어떤 특성을 기준으로 여러 데이터를 정렬시키는 처리입니다.
정렬에는 대표적으로 다음과 같은 방법들이 있습니다.
1. 버킷 정렬
2. 기수 정렬
3. 선택 정렬
4. 버블 정렬
5. 삽입 정렬
6. 셀 정렬
7. 병합 정렬
8. 퀵 정렬
9. 힙 정렬
1. 버킷 정렬
가장 간단한 정렬 알고리즘이고, 처리가 간단한 대신 메모리 자원을 많이 소모한다고 합니다.
데이터의 범위(최댓값 - 최솟값) 만큼의 배열을 준비하고 요소들을 -1(Empty)로 설정합니다. 데이터들을 번호에 맞춰 배열에 저장합니다(빈틈없게 아님. 저장하려는 데이터가 요소 번호와 일치하는 배열 요소에 그대로 저장). 그 후 1번째 배열부터 데이터를 가져옵니다. 그러면 자동으로 정렬이 완료됩니다.
즉, 정렬하려는 값들의 최소값부터 최댓값만큼의 배열을 준비해서 배열 번호와 일치하게 데이터를 넣은 다음, 빈 값이 아닌 배열만 다시 추출을 하는 것입니다.
2. 기수 정렬(Radix sort)
버킷 정렬을 반복하는 정렬입니다.
10진수의 경우 0~9까지의 배열을 만듭니다.
정렬하려는 수를 낮은 자릿수부터 기준으로 해서 배열에 버킷 정렬을 합니다.
정렬이 끝나면 그다음 자릿수(10의 자리)에 해당하는 수를 버킷 정렬합니다. 정렬할 때는 먼저 들어간 수부터 꺼내오고 다 꺼내면 다음 배열로 이동합니다. 0 -> 9 순서로 진행합니다.
최종 자릿수까지 끝나면 앞에서부터 꺼내옵니다.
시간 복잡도 : O(dn)
참고 = lktprogrammer.tistory.com/48
3. 선택 정렬
선택 정렬은 이미 정렬된 부분과 정렬되지 않은 부분으로 나뉩니다. 정렬되지 않은 부분에서 비교를 통해 최소(또는 최대) 값을 찾아 가장 처음 부분에 저장합니다. 이 저장된 영역이 정렬된 부분이 됩니다. 이후 이 과정을 반복해 차례대로 저장하면 정렬이 완료됩니다.
시간 복잡도 : O(n²)
4. 버블 정렬
선택 정렬과 마찬가지로 정렬된 부분과 정렬되지 않은 부분으로 나뉩니다. 정렬되지 않은 부분에서 처음 데이터를 바로 다음 데이터와 비교합니다. 만약 그다음 데이터가 더 작으면 두 요소의 위치를 바꿉니다. 그렇지 않으면 그대로 둡니다. 검사 위치를 한 칸 오른쪽으로 이동시켜서 다시 위의 과정을 실행합니다. 요소의 끝에 다다르면, 여기서는 최댓값이 가장 오른쪽에 위치하게 되고 다시 처음으로 되돌아가 같은 처리를 반복합니다.
시간 복잡도 : O(n²)
5. 삽입 정렬
정렬되지 않은 부분의 데이터를 정렬된 부분의 데이터와 비교하여 적절한 위치에 끼워 넣는 정렬입니다. 2번째부터 검사를 시작하며 정렬되지 않은 부분의 데이터를 정렬된 데이터와 차례로 비교합니다. 조건을 만족하면 해당 위치 이후의 데이터들을 1칸씩 뒤로 미루고 데이터를 끼워 넣습니다. 같은 처리를 정렬이 완료될 때까지 반복합니다.
시간 복잡도 : O(n²)
6. 셀 정렬
이웃한 데이터를 비교하지 않고, 일정 길이만큼 그룹을 만들어서 각 그룹별로 정렬을 합니다. 약간 복잡한 과정을 거치지만 값을 이동시키는 횟수를 줄일 수 있기 때문에 시간 복잡도가 O(n^1.25)로 버블 정렬이나 삽입 정렬보다 빠릅니다. 그룹으로 만들 길이는 임의로 정할 수 있습니다.
시간 복잡도 : O(n^1.25)까지 가능
7. 병합 정렬
무리를 절반씩 나눠서 무리에 속한 숫자의 수가 1이 될 때까지 나눕니다.
나눠진 무리들을 2 무리씩 짝지어 비교하고 합치면서 정렬을 실행합니다.
최종적으로 1개의 무리만 남을 때까지 합치면 정렬된 배열을 얻습니다.
시간 복잡도 : O(n log n)
8. 퀵 정렬
정렬을 할 숫자 중에 임의로 하나를 선택해 기준(피봇)으로 삼습니다. 이 기준을 중심으로 비교를 해서 작으면 왼쪽 크면 오른쪽으로 정렬합니다.
그러면 좌, 우 영역은 아직 정렬이 되지 않은 상태이므로 같은 과정을 정렬이 될 때까지 진행합니다.
시간 복잡도 : O(n log n)
9. 힙 정렬
힙의 의미는 2가지로 쓰입니다. 첫째는 정렬에서의 힙이고, 둘째는 메모리에서의 힙입니다.
힙은 트리 구조의 종류로 힙 형태의 구조를 만들면 루트(가장 처음 부분)가 가장 작거나 가장 큽니다.
따라서 루트의 값을 가져와서 배열에 넣고 남은 힙을 다시 규칙(자료구조에서의 힙 구조)에 따라 정렬합니다.
위와 같은 방법을 반복하면 정렬된 배열을 얻을 수 있습니다.
시간 복잡도 : O(n log n)
정렬에 관한 정보 : namu.wiki/w/%EC%A0%95%EB%A0%AC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#s-2.4.3
검색
검색
여러 개의 데이터 안에서 원하는 데이터를 찾아내는 알고리즘입니다.
검색의 대표적인 종류는 다음과 같습니다.
1. 순차 검색
2. 이진 검색
3. 문자열 검색
1. 순차 검색
1번째 디에터부터 조사하여 비교하는 방법입니다.
평균적으로 N/2번 비교해야 하기 때문에 데이터 양이 많을 때는 좋지 않은 방법입니다.
데이터가 저장된 요소와 비교할 대상을 비교해가며 다르면 다음 순서로 넘어가 검사를 계속합니다.
2. 이진 검색
데이터가 오름차순이나 내림차순으로 정렬이 되어 있을 때, 검사대상을 절반씩 줄여가며 찾는 방법입니다.
처음에 중앙값 M을 정하고 그 값보다 크면 큰 값 영역의 중간지점으로 이동하고 검사하는 처리를 원하는 데이터를 찾을 때까지 반복합니다.
3. 문자열 검색
주어진 문자열에서 찾고자 하는 문자열이 있을 때, 해당 문자열의 위치를 찾는 알고리즘입니다.
찾으려는 문자열과 조사할 문자열이 배열로 있을 때, 찾으려는 문자열의 첫 번째 배열을 조사할 문자열의 배열과 차례대로 비교하고, 서로 같으면 다음 문자열을 비교해서 일치하는 부분을 찾아냅니다.
마치며...
이것을 마지막으로 책을 하나 다 보았습니다.
알고리즘들이 어떤 처리과정을 거쳐 문제를 해결하는지 알게되어 유익한 시간이었던 것 같습니다.
알고리즘의 기본 요소부터 자료구조, 알고리즘(정렬과 검색) 그리고 알고리즘의 평가방식까지 알아봤는데, 나중에 필요하면 더 세세하게 배우겠지만 앞으로 관련 지식을 접하면 좀 더 친숙하게 느껴질 것 같습니다.
그리고 책에 대해서 잠깐 얘기를 해보자면, 장단점이 있습니다.
우선, 장점은 책이 이뻐서 공부하고 싶은 욕구를 불러일으키고, 타입과 값처럼 기본적인 것부터 다루면서, 기존에 알고 있던 변수 같은 개념이 왜 그런 형태를 가지는지에 대해 좀 더 본질적으로 알 수 있었습니다.
단점은 일본인 저자가 지은 것을 옮겨서 그런지 코딩할 때 잘 쓰지 않는 용어로 설명이 되어있는 부분이나 예시에서 변수명을 선언할 때 예를 들면 성적을 나타내는 변수명이 "JUMSU"같이 영어인데 한글인 부분은 아쉬웠습니다. 문제 되는 건 아니지만 뭔가 전문적이지 않아 보이는...?
그리고 설명이 좀 복잡하게 되어있어서 조금 복잡한 개념들은 이해하기가 너무 어려웠습니다. 그래서 다른 자료나 책들도 조금 참고를 해야 했습니다.
그래도 처음 알고리즘을 공부해야겠다고 생각이 들고나서 가장 먼저 보고 싶었던 책이기 때문에 매력은 있는 것 같습니다.
정보문화서 출판사의 "그림으로 정리한 알고리즘과 자료구조"도 도움이 굉장히 많이 되었습니다.
감사합니다.