정렬

정렬 

- 데이터를 특정한 기준에 따라서 순서대로 나열한 것

 

- 프로그램에서 데이터를 가공할 때 오름차순이나 내림차순 등 대부분 어떤 식으로든 정렬해서 사용하는 경우가 많다.

 

- 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색(binary search)이 가능해진다.

 

- 정렬 알고리즘의 종류

1. 선택 정렬
2. 삽입 정렬
3. 퀵 정렬
4. 계수 정렬

선택 정렬

- 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복

- 가장 작은 것을 선택한다는 의미에서 '가장 원시적인 방법'

 

선택 정렬 예시

이중 for문을 통해서, i번째 값을 최솟값으로 지정한 후, i번째 이후의 값들과 비교하여 최솟값을 정한뒤, i번째에 해당 최솟값을 갱신한다. 

선택 정렬은 N-1 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야하고, 매번 가장 작은 수를 찾기 위해 비교 연산이 필요로 한다.

 

선택 정렬의 시간복잡도

위 코드는 N+(N-1)+(N-2)+ ... +2 의 연산 횟수를 갖기 때문에 N x (N + 1) / 2 번 연산을 수행한다.

이는 빅오 표기법으로 간단히 O(N^2)이라고 표현할 수 있다.

즉, 선택 정렬의 시간 복잡도는 2중 반복문이 사용되었기 때문에 O(N^2)이다. 

 

선택 정렬은 기본 정렬 라이브러리를 포함해 다른 알고리즘과 비교했을 때, 매우 비효율적이지만,

특정 리스트에서 가장 작은 데이터를 찾는 일이 코딩테스트에서 잦기 때문에, 알아둘 필요가 있다.

 

 

삽입정렬

- 데이터를 하나씩 확인하며, 적절한 위치에 삽입

- 필요할 때만 위치를 바꾸기 때문에, '데이터가 거의 정렬 되어 있을 때' 훨씬 효율적

- 첫 번째 데이터는 정렬되어있다고 가정하기 때문에, 두 번째 데이터부터 비교하기 시작

 

삽입 정렬 예시

이중 for문을 통해 i번째부터 그 이하 번째의 값들을 비교해서, 만약 이전의 데이터값이 더 크다면, 그 위치를 앞뒤로 바꿔주는 과정을 0번째 값까지 확인한다. 중간에 이전의 데이터값이 더 작다면, 더 이상 바꿔줄 위치가 존재하지 않기 때문에, break문으로 반복문을 중단하고 다음 index의 데이터값을 비교하기 시작한다.

 

 

삽입정렬의 시간복잡도

삽입 정렬도 선택 정렬과 마찬가지로 이중 for문을 사용하면서 시간 복잡도가 O(N^2)이다. 하지만 삽입 정렬의 경우, 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작하기 때문에, 최선의 경우 O(N)의 시간복잡도를 가질 수 있다.

즉, 삽입 정렬은 데이터의 정렬 상태에 따라, 효율성이 달라진다.

 

 

퀵 정렬

- 기준 데이터(Pivot)를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다

- 큰 데이터와 작은 데이터의 위치를 바꾼 후, 반으로 나누는 방식

- 피벗을 설정하고 리스트를 분할하는 방법에 따라 여러 방식 존재

- 호어 분할(Hoare Partition) : 리스트에서 첫 번째 데이터를 피벗으로 정한다.

 

퀵 정렬 예시

pivot을 리스트에서 첫 번째 데이터로 정하기 때문에, pivot을 start로 초기화 해주고, 그 다음 데이터를 left, 마지막 데이터를 right로 초기화 해준다.

 

left값이 right값을 역전할 때까지 반복문을 수행하고, 각각 left번째 값과 right번째 값이 범위를 벗어나지 않는 조건에서, pivot번째 값보다 크고 작은 값을 찾을 때까지 left, right값에 변화를 준다.

각각 pivot번째 값보다 크고 작은 값을 찾을 때의 left, right값을 비교해서, 만약 left값이 right값보다 크다면, 즉 서로 엇갈렸다면, pivot과 right값을 교체해주고, 그렇지 않았다면, 즉 엇갈리지 않았다면, left, right번째 값들을 서로 교환해준다.

 

반복문을 빠져나올 때까지 위 과정을 반복해주고, 수정된 array값을 토대로 quick_sort 함수를 array값들이 완전히 정렬이 될 때까지 반복한다. 

 

분할 후, quick_sort함수에서 right 값을 기준으로 각자 정렬을 수행하는 이유는, 분할이 될 때의 기준값이 pivot과 교체되는 right값이기 때문이다.

 

 

파이썬의 장점을 살린 퀵 정렬 예시

기존의 퀵 정렬의 분할 방식과는 조금 다르다.

피벗과 데이터를 비교하는 비교 연산 횟수가 증가하므로, 시간 면에서는 조금 비효율적이다

하지만 더 직관적이고 기억하기 쉽다.

 

 

퀵 정렬의 시간 복잡도

앞서 다룬 선택 정렬와 삽입 정렬의 시간 복잡도는 O(N^2). 최악의 경우에도 항상 O(N^2)

퀵 정렬의 평균 시간 복잡도는 O(NlogN)

최선의 경우 : 8개의 데이터를 정확히 절반씩 나누는 경우 

최악의 경우 : 가장 왼쪽 데이터를 피벗으로 삼을 때, '이미 데이터가 정렬 되어 있는 경우' -> O(N^2)

                  삽입 정렬과 정반대.

 

 

 

계수 정렬

- 특정한 조건이 부할할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘

- 데이터의 개수 N, 데이터 중 최댓값 K인 경우, 최악의 경우에도 수행시간 O(N+K)

- 다만, 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용 -> 모든 범위를 담을 수 있는 크기의 리스트를 선언해야 하기 때문

- 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용가능

- 앞서 다룬 3가지 정렬 알고리즘처럼 직접 데이터의 값을 비교한 뒤에 위치를 변경하는 방식이 아님

- 리스트의 모든 데이터를 0으로 초기화 한 후, 데이터를 하나씩 확인하며, 데이터값에 해당하는 index번째 값을 증가시킨다.

 

계수 정렬 예시

count 리스트는 0도 포함되기 때문에 최댓값에서 1 추가한 만큼 리스트를 만들어준다.for문으로 array에 있는 데이터값을 확인하여 해당 번째 count값을 증가시킨다.이중 for문을 통해 순서대로 count에 있는 개수만큼 해당 데이터를 출력한다.

 

 

계수 정렬 공간 복잡도

- 계수 정렬의 시간 복잡도와 공간 복잡도 모두 O(N + K)

- 계수 정렬은 때에 따라서 심각한 비효율 발생

  ex) 데이터가 0와 999,999로 단 2개만 존재 -> 데이터가 2개만 존재하지만, 0~999,999의 리스트를 만들기 때문에 비효율

- 계수 정렬은 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적으로 사용

  ex) 성적 100명 여러 명

 

 

 

파이썬 정렬 라이브러리

파이썬은 기본 정렬 라이브러리인 sorted() 함수를 제공한다. sorted()는 퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 만들어졌는데, 병합 정렬은 일반적으로 퀵 정렬보다 느리지만 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다.

 

sorted() 함수는 리스트, 딕셔너리 자료형 등을 입력받아 정렬된 결과를 출력한다. 집합 자료형이나 딕셔너리 자료형을 입력받아도 반환 결과는 리스트 자료형이다.

 

sorted 예시

 

 

리스트 변수가 하나 있을 때 내부 원소를 바로 정렬할 수 있다.

리스트 객체의 내장 함수인 sort()함수를 이용하면 별도의 정렬된 리스트를 변환하지 않고 내부 원소가 바로 정렬된다

 

sort 예시

 

 

또한 sorted()나 sort()를 이용할 때 key 매개변수를 입력 받을 수 있다.

key 값으로는 하나의 함수가 들어가야 하며 이는 정렬 기준이 된다.

 

key를 활용한 예시

 

 

정렬 라이브러리의 시간 복잡도

정렬 라이브러리는 항상 최악의 경우에도 O(NlogN)의 시간 복잡도를 보장한다.

문제에서 별도의 요구가 없다면 기본 정렬 라이브러리를 사용하는 것이 좋다.

데이터 범위가 한정되어 있고 더 빠르게 동작해야 할 때는 계수 정렬 사용

 

코딩 테스트에서 정렬 알고리즘이 사용되는 경우 3가지

1. 정렬 라이브러리로 풀 수 있는 문제 : 단순 정렬 기법을 알고 있는지 물어보는 문제. 기본 정렬 라이브러리의 사용 방법 숙지하고 있으면 어렵지 않게 풀이 가능
2. 정렬 알고리즘의 원리에 대해 물어보는 문제 : 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알고 있어야 문제 풀이 가능
3. 더 빠른 정렬이 필요한 문제 : 퀵 정렬 기반의 정렬 기법으로는 풀 수 없으며, 계수 정렬 등의 다른 정렬 알고리즘을 이용하거나 문제에서 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 풀이 가능

 

 

 

위에서 아래로

문제 : 교재 178p 참고

 

가장 기본적인 정렬을 할 수 있는지 물어보는 문제

수의 개수가 500개 이하, 모든 수는 1 이상 100,000 이하 이므로, 어떤 알고리즘을 사용해도 상관없지만, 코드가 간결해지는 기본 정렬 알고리즘을 이용하는 것이 효과적

 

나의 풀이

간단히 풀이되는 문제이다. 입력받은 값을 리스트에 삽입하고, 해당 리스트를 sort() 함수를 사용하여 정렬하고 출력한다.

해설코드는 본인 코드와 큰 차이가 없어서 생략하겠다

해설 코드는 sorted() 함수를 사용하여 다른 변수에 정렬된 리스트를 옮긴 후, 출력하였다.

 

 

 

성적이 낮은 순서로 학생 출력하기

문제 : 교재 180p 참고

 

해당 문제는 학생의 정보가 최대 100,000개까지 입력될 수 있으므로, 최악의 경우 O(NlogN)을 보장하는 알고리즘을 이용하거나, O(N)을 보장하는 계수 정렬을 이용하면 된다.

 

나의 풀이

student라는 리스트에 데이터를 2개씩 삽입하고, sorted() 함수로 정렬을 하되, key값을 사용하여, 데이터의 1번째 값을 기준으로 정렬을 하고, 출력한다.

 

 

해설을 참고한 코드

해설에서는 sorted() 함수에서 사용되는 key값을 넣을 때, 일반 함수를 따로 만들지 않고, 람다함수를 사용하여, 데이터의 1번째 값을 기준으로 정렬하게 만들었다.

확실히 1회성으로 사용되는 함수의 경우, 굳이 함수를 생성하지 않고, 람다함수로 간단히 처리하는 것이 훨씬 간결하고 보기 좋은 것 같다. 람다 함수에 익숙해지도록 연습해야겠다.

 

 

 

두 배열의 원소 교체

문제 : 교재 182p 참고

 

문제 풀이의 기본 아이디어는 A에 가장 작은 원소를 골라서 B의 가장 큰 원소와 교체하는 것이다. 

A에서 교체할 원소가 B에서 교체할 원소보다 작은 경우에만 교체한다.

 

나의 풀이

데이터 값들을 입력받고, 리스트 a는 오름차순, b는 내림차순으로 정렬하였다.

a, b 각각 0번째부터, 가장 작고 큰 순서대로 정렬되어있다.

최대 k번 교체가 가능하기 때문에 k번 반복하여 각 배열에 같은 위치에 있는 값들을 비교하여, 교체가 필요할 때만 교체한다.

 

해설의 코드와 거의 동일하여 해설 코드는 생략하겠지만, 해설 코드에서는 배열의 값들을 더할 때, 본인 코드처럼 for문을 사용하지 않고, sum() 함수를 사용하였다.

나중에 배열의 합을 구할 경우가 생기면 sum() 함수를 기억해서 사용해야겠다.

 

 

 

느낀점

퀵 정렬을 제외하고는 전반적으로 난이도가 크게 어렵진 않았다. 이번 part의 실전 문제의 난이도가 평이해서 그런지, 기본 라이브러리를 사용하여 문제를 풀어서 그런지 크게 어려움은 없었다. 

하지만, 기본 라이브러리를 사용하지 못하고, 이번에 배운 정렬들로만 문제를 풀어야 하는 상황이 생긴다면, 문제를 풀 때, 고민을 좀 하게 될거 같다. 

이번 part에서 시간 복잡도에 대한 내용도 좀 있어서 문제를 접할 때, 어느정도 유의하며 풀어야 한다는 것을 느꼈다.

열심히 풀었는데, 시간초과가 발생하면 안되니까....