[알고리즘/Algorithm]정렬(Sorting)
🔷 정렬(Sorting)
정렬(Sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 프로그램에서 데이터를 가공할 때 오름차순 혹은 내림차순으로 정렬하여 사용하는 경우가 많기에 프로그램 작성 시 가장 많이 사용되는 알고리즘이다.
* 이진탐색(Binary Search)을 하기 위한 전처리 과정이니 꼭 알아두어야 한다.
🔷 정렬의 종류
◼ 선택정렬(Selection Sort)
가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고 그 다음 가장 작은데이터를 선택하여 앞에서 두 번째 데이터와 바꾸는 과정을 반복시키는 것으로 시간 복잡도는 O(N^2) 이다.
* Swap 소스코드 : 파이썬에서는 array[1], array[2] = array[2], array[1] 로 두 원소의 위치 변경이 가능하다. (보통은 temp 임시변수 선언)
◼ 삽입 정렬(Insertion Sort)
데이터를 하나씩 확인하며 각 데이터를 적절한 위치에 삽입한다는 의미로, 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에 그 위치에 삽입된다. 이 때 특정 데이터가 적절한 위치에 들어가기 이전에 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다.
* range : range의 매개변수는 3개로 range(start, end, step)이고, start에서 시작하여, end로 끝나고 step에 -1이 들어가면 1씩 감소한다.
◼ 퀵 정렬(Quick Sort)
퀵 정렬은 정렬 알고리즘 중에 가장 많이 사용되는 알고리즘이다. 퀵 정렬의 원리는 '기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다' 라는 원리에서 동작한다.
1. 기준데이터를 설정한다( pivot = 기준데이터(첫번째 데이터))
2. 왼쪽에서부터 pivot 보다 큰 데이터를 찾고 오른쪽에서는 pivot 보다 작은 데이터를 찾고 위치를 변경한다.
3. 1,2 과정을 반복하다가 왼쪽과 오른쪽이 엇갈렸을 때 작은 데이터와 피벗의 위치를 바꾼다.
4. 이 때 pivot 을 기준으로 왼쪽의 데이터는 pivot 보다 작고 오른쪽 데이터는 pivot 보다 큰 상태로 정렬되어진다.(분할완료)
5. 그 후 왼쪽과 오른쪽 각각 위 과정을 반복시킨다.
파이썬에서는 더 간결하게 퀵정렬 코드를 작성할 수 있다.
퀵 정렬의 시간 복잡도는 O(NlogN)이 되어 앞에서 다룬 선택정렬과 삽입정렬에 비해 매우 빠른편이다.
◼ 계수정렬(Count Sort)
계수정렬은 특정한 조건이 부합할 때만 사용할 수 있고 매우 빠른 정렬 알고리즘이다.
* 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능
* 가장 작은 데이터와 큰 데이터의 차이가 1000000 을 넘지 않을 때 효율적이다.
계수 정렬은 단순하게 정렬할 배열의 값을 새로 만든 배열의 인덱스에 넣어 갯수를 카운트하는 방식이다.
🔷 정렬 라이브러리(Python)
- array.sort()
- array1 = sorted(array2)
◼ 참고
- 이것이 취업을 위한 코딩 테스트다 with 파이썬