[자료구조와 알고리즘] Sorting
Sorting
Sorting Algorithms
- Bubble sort
- Insertion sort
- Quick sort
Sorting이란 크기 순으로 오름차순 정렬된 리스트로 모든 아이템을 배치하는 것을 말한다.
숫자가 212인 item이 여러개가 있기 때문에 숫자를 key값으로 sorting하게 되면 이들 간의 순서를 정하기가 모호하다.
이 때 같은 numeric key에 대한 item들이 unstorted data에서 정렬된 순서가 sorted data에 반영된 순서로 정렬되면 Stable sort, 그렇지 않으면 Unstable sort라고 한다.
Stable sort
- 같은 key를 갖는 데이터가 그들의 relative input order를 output에서 유지하는 방식
복잡하고 성능이 좋은 sort는 O(nlogn)의 시간복잡도를 갖는다.
quick sort는 O(n2)의 시간복잡도를 갖는데 어느 경우에 n2을 갖는데 굉장히 희박하게 갖는 것이기 때문에 quick sort는 코드를 조금만 바꾸면 nlong의 시간복잡도를 가져서 사실상 O(nlogn)으로 생각해도 큰 문제가 없다.
- 정렬이 하나도 되어있지 않은 경우에만 O(n2)
실제 시스템에 적용했을 때 속도가 빠른 sort는 quick sort이다.
같은 nlogn이지만 실제 적용했을 때 heap이나 merge에 비해서 평균적으로 더 빠르기 때문에 quick sort를 굉장히 많이 사용한다. 프로그램 언어마다 sorting을 해주는 라이브러리를 만들어 놨는데 c++,java의 sorting 알고리즘에서 quick sort를 사용한 것이고 파이썬의 내장 sort 함수들은 merge sort를 사용한 것이다.
Bubble sort algorithms
리스트에서 인접한 element들을 비교한 후에 크기 순으로 올바르게 배치하는 방식이다.
리스트 안의 item들이 올바르지 않은 순서라면, 각각의 인접한 item들을 swapping하면서 작동한다.
- n개의 item에 대해 비교를 할 때 (n-1) 번의 비교가 진행된다.
- (맨 마지막에 하나 남은 경우는 당연히 제일 작은 값일 것이기 때문에 할 필요가 없어서 sorting이 그대로 끝나기 때문에 n-1번의 process가 진행되는 것)
The 1st iteration
6개의 데이터를 왼쪽부터 시작하여 쭉 비교하면서 제일 큰 값을 맨 오른쪽에 넣은 모습을 볼 수있다.
그러면 맨 끝 값은 sorting이 완료되었다고 보고 다시 남은 5개의 item에 대해서 sort(iteration)를 진행하는 것이다.
Why Bubble?
첫 값인 45인 값이 bubble과 같이 솟아올라 오른쪽으로 흘러간다. 흘러가면서 비교하다가 현재 bubble보다 더 큰 값이 나오면 해당 bubble이 툭 튀어올라서 해당 bubble이 오른쪽으로 흘러가게 된다.
이처럼 값이 정렬되는 방식이 bubble과 같이 보인다 하여 bubble sort라는 이름이 붙여지게 되었다.
The 2nd iteration
The 3rd iteration
The 4th iteration
The 5th iteration
리스트에 n개의 원소가 있을 때, 최대 operation의 횟수는 n-1번이고 n/2번 반복하기 때문에
(n-1) * n/2 라서 O(n2)의 시간복잡도를 갖는 것이다.
- (n-1) + (n-2) + … + 1
- (n-1)(n-1+1) / 2
코드로 구현
def bubble_sort(unordered):
iteration = len(unordered)-1 # n-1
for i in range(iteration): # 0~n-2
for j in range(iteration - i): #각 iteration에서 뒤져봐야 되는 index의 범위
if unordered[j] > unordered[j+1]:
unordered[j], unordered[j+1] = unordered[j+1], unordered[j]
test = [45, 23, 87, 12, 32, 4]
bubble_sort(test)
print(test)
# [4, 12, 23, 32, 45, 87]
j - for 문이 한 번 돌 때마다 현재 리스트에서 제일 큰 값이 제일 오른쪽에 배치되게 된다.
Insertion sort algorithms
삽입 정렬 알고리즘은 항상 정렬된 상태의 서브 리스트를 유지하고, 다른 나머지 비율은 정렬되지 않은 상태로 남아있다.
방식은 정렬되지 않는 서브 리스트로부터 element를 한 개씩 취하여 정렬된 서브 리스트의 알맞은 위치에 그 element들을 삽입하는 방식이다.
그래서 서브리스트는 정렬된 채로 남아있는 것이다.
다음과 같은 배열을 생각해 보자.
알고리즘은 1번과 4번 인덱스들 사이를 돌기위해 for loop를 사용하면서 시작한다.
핵심 아이디어는 0번 인덱스는 이미 정렬된 상태의 서브리스트로 보는 것이다. 그렇기 때문에 1번 index부터 시작할 것이다.
즉, 0번 index의 ‘5’ 카드를 쥐고 있다고 생각하면 이를 정렬할 필요가 없다는 의미인 것이다.
그런데 딜러가 다음 카드인 1번 인덱스의 1이라는 카드를 주었다. 그러면 이 때는 sorting된 상태를 유지하면서 내 손에 가진 덱의 가장 마지막 값부터 비교하여 알맞은 위치에 삽입시킬 것이다. 1과 5를 비교했을 때 1이 5보다 작기 때문에 5의 왼쪽에 삽입하였다.
이와 같은 과정을 모든 element에 대해서 진행한다.
딜러가 주는 카드덱(오른쪽 서브리스트)에서 한 장씩 카드를 나에게 주는데 내 손에 있는 카드덱의 가장 큰 것부터 비교하기 때문에 me<dealer 일 때까지 swapping을 하는 것이다.
n-1번의 iteration을 평균 n/2번 진행한다.
코드로 구현
def insertion_sort(unordered):
for i in range(1, len(unordered)):
key = unordered[i] #딜러한테 새로 받는 카드
j = i # 이 순간 받은 카드도 내 손의 카드에 속하게 된다.
while j > 0 and unordered[j-1] > key: # 내 손의 카드의 가장 마지막 값부터 시작하여 비교
unordered[j] = unordered[j-1] # 바꿔야 되면 큰 걸 앞으로 땡겨온다.
j-=1 # 그 다음 값으로 이동
unordered[j] = key # while문이 통과되면 key값이 제 자리(j)를 찾은 것이므로 삽입
test = [45, 23, 87, 12, 32, 4]
insertion_sort(test)
print(test)
[4, 12, 23, 32, 45, 87]
Quick sort algorithms
Quick sort 알고리즘은 매우 효율적인 sorting 방식이다. 더 구체적으로 퀵정렬은 문제를 해결하기가 훨씬 더 쉬운 작은 서브 문제들로 나누는 merge sort 알고리즘과 유사한 알고리즘의 종류인 분할정복 알고리즘이다.
이 알고리즘은 정렬되지 않은 배열을 두 개의 sub-array로 나누는 것이 핵심 아이디어이다.
구조상으로는 모든 elements가 분기점(pivot이라고도 함)을 기준으로 왼쪽 부분에 있는 모든 element들은 그 값보다 작은 값을 pivot의 오른쪽 부분의 모든 element들은 pivot 값보다 더 큰 값을 가진 애들만 있게 된다.
첫 번째 iteration 이후에 두 개의 정렬되지 않은 sub-list를 얻고 이러한 두 sub-list위에서 똑같은 process가 진행된다.
따라서 퀵정렬 알고리즘은 리스트를 두 부분으로 나눠서 전체 리스트를 정렬하기 위해 두 개의 서브 리스트로 계속 나눠서 재귀적으로(recursively) 퀵 정렬을 적용한다.
4번째 단계에서 left pointer와 right pointer가 더 이상 움직이지 못하기 때문에 두 값의 위치를 바꾸어 주고 계속 진행한다. (포인터는 바뀌지 않는 것임에 유의한다.)
- 정상이면 멈출 필요가 없기 때문에 다음 값을 보기 위해서 pointer를 움직이는 것이고 만약 비정상적이면 멈춰서 값을 바꿀 준비를 하는 것이다.
- OK면 넘어가!
위와 같은 과정이 끝나는 조건은 left pointer와 right pointer가 서로 교차 되었을 때이고 이 때 right pointer의 데이터와 pivot 데이터를 swap 하면 pivot 값인 45를 기준으로 왼쪽 오른쪽에 각각 작은값과 큰 값이 들어가지게 된다.
물론 이때 양 옆 서브 리스트들은 정렬되지 않은 상태이다.
자, 그래서 우리는 두 개의 sub-list를 얻었고 똑같은 과정을 이 두 서브리스트들에 대하여 재귀적으로 퀵 정렬 알고리즘을 적용할 것이고 전체 모든 리스트가 정렬될 때까지 반복할 것이다.
- 왼쪽 서브 리스트에서 pivot값인 4를 기준으로 정렬을 진행하고 마지막 과정에서 4에 right pointer가 위치하여 right pointer와 pivot 값을 바꾸어 주어야 하는데 두 값이 같은 값을 가리키기 때문에 그대로 두는 것이다.
# pivot을 기준으로 양 옆 값을 정하고 궁극적으로 pivot index를 반환해 주는 함수
def partition (unsorted, first, last):
pivot = unsorted[first]
left = first + 1
right = last
while True:
while unsorted[left] <= pivot and left < last:
left += 1
while unsorted[right] > pivot and right >= first: # right이 pivot까지 가도 OK
right -= 1
if left < right:
unsorted[left], unsorted[right] = unsorted[right], unsorted[left]
else:
break
unsorted[first], unsorted[right] = unsorted[right], unsorted[first]#swap(pivot right)
return right # pivot index
def quick_sort(unsorted, first, last):
if first < last:
pivot_index = partition(unsorted, first, last)
quick_sort(unsorted, first, pivot_index-1) # 왼쪽 sub-list에 대해서 또 진행
quick_sort(unsorted, pivot_index+1, last) # 오른쪽 sub-list에 대해서 또 진행
# 만약 first와 last가 같아지면 (sub-list의 크기가 1) 그냥 return 한다.
test = [45, 23, 87, 12, 32 ,4]
quick_sort(test, 0, len(test) - 1)
print(test)
Sort Functions in Python
sorting을 위한 python
- sort()
- sorted()
Lambda functions
- A lambda function is a small anonymous function object
- It can have many parameters, but can have only one expression
>>> def temp(a, b):
return a + b
>>>
>>> temp(2, 3)
5
>>>
>>> x = lambda a, b: a + b
>>>
>>> x(3, 4)
7
>>>
>>> def base(n):
return lambda a: a * n
>>>
>>> doubler = base(2) # doubler : a * 2
>>> tripler = base(3) # tripler : a * 3
>>>
>>> doubler(11)
22
>>> tripler(11)
33
위처럼 람다 함수 자체가 반환이 되기도 함
Python sort()
- sort() is a member function of the list class
- It is implemented using Timsort, which is based on Merge sort and this stable.
>>> numbers = [3, 8, 5, 1]
>>> numbers.sort()
>>> numbers
[1, 3, 5, 8]
>>>
>>> numbers.sort(reverse=True)
>>> numbers
[8, 5, 3, 1]
>>>
>>> tuples = [(2, 2), (3, 4), (4, 1), (1, 3)]
>>> tuples.sort()
>>> tuples
[(1, 3), (2, 2), (3, 4), (4, 1)]
>>>
>>> tulples.sort(key=lambda x: x[1]) # tuple의 두 번째 element를 기준으로 sorting
>>> tuples
[(4, 1), (2, 2), (1, 3), (3, 4)]
>>>
>>> test = [(2, 'b'), (3, 'd'), (3, 'a'), (1, 'c')]
>>> test.sort()
>>> test
[(1, 'c'), (2, 'b'), (3, 'a'), (3, 'd')]
>>>
>>> test = [(2, 'b'), (3, 'd'), (3, 'a'), (1, 'c')]
>>> test.sort(key=lambda x: x[0])
>>> test
[(1, 'c'), (2, 'b'), (3, 'd'), (3, 'a')]
>>>
>>> test = [(2, 'b'), (3, 'd'), (3, 'a'), (1, 'c')]
>>> test.sort(reverse=True)
>>> test
[(3, 'd'), (3, 'a'), (2, 'b'), (1, 'c')]
>>>
>>> test = [(2, 'b'), (3, 'd'), (3, 'a'), (1, 'c')]
>> test.sort(key=lambda x: (-x[0], x[1]))
>>> test
[(3, 'a'), (3, 'd'), (2, 'b'), (1, 'c')]
>>>
>>> test = [(2, 'b'), (3, 'd'), (3, 'a'), (1, 'c')]
>>> test.sort(key=lambda x: x[1], reverse=True) # (3, 'd'), (1, 'c'), (2, 'b'), (3, 'a')
>>> test.sort(key=lambda x: x[0])
>>> test
[(1, 'c'), (2, 'b'), (3, 'd'), (3, 'a')]
>>>
- 별도로 지정을 하지 않은 경우 첫 번째 element가 같은 경우 두 번째 element를 기준으로 정렬한다.
- sort()
- 그러나 key=lambda x: x[0] 를 명시하여 첫 번째 element를 기준으로 정렬을 하겠다 하면 그 값이 같은 경우에 두 번째 element에 대하여는 original의 순서를 그대로 사용하는 stable 정렬 방식이다.
Python sorted()
- sorted() is a built-in function of Python
- It receives list tuple, set, string, and returns the sorted list
>>> data = [3, 8, 5, 1]
>>> data.sort()
>>> data
[1, 3, 5, 8]
>>>
>>> data = [3, 8, 5, 1]
>>> data1 = sorted(data)
>>> data1
[1, 3, 5, 8]
>>> data
[3, 8 ,5 ,1]
>>>
>>> data = (3, 8, 5, 1)
>>> data1 = sorted(data)
>>> data1
[1, 3, 5, 8]
>>> data
(3, 8, 5, 1)
>>>
>>> data = {3, 8, 5, 1}
>>> data1 = sorted(data)
>>> data1
[1, 3, 5, 8]
>>> data
{8, 1, 3, 5} # data의 순서가 바뀌어 있는데 set object이기 때문에 순서는 상관없다.
- (Bubble or Insertion Sort) and Quick sort
- 배열 하나는 asending 으로 하면 되고 나머지 하나는 descending order로 해야 하기 때문에 이 때 부호를 마이너스로 바꾸어 sorting을 진행하면 해결된다.
def bubble_sort(unordered):
iteration = len(unordered) - 1
for i in range(iteration):
for j in range(iteration - i):
if unordered[j] > unordered[j+1]:
unordered[j], unordered[j+1] = unordered[j+1], unordered[j]
n = int(input())
_a = list(map(int, input().split()))
_b = list(map(int, input().split()))
minus_b = list(map(lambda x: -x, _b))
bubble_sort(_a)
bubble_sort(minus_b)
_b = list(map(abs, minus_b))
print(sum(_a[i] * _b[i] for i in range(len(_a))))
import sys
def partition(unsorted, first, last):
pivot = unsorted[first]
left = first + 1
right = last
while True:
while unsorted[left] <= pivot and left < last:
left += 1
while unsorted[right] > pivot and right >= first:
right -= 1
if left < right:
unsorted[left], unsorted[right] = unsorted[right], unsorted[left]
else:
break
unsorted[first], unsorted[right] = unsorted[right], unsorted[first]
return right # pivot index
def quick_sort(unsorted, first, last):
if first < last:
pivot_index = partition(unsorted, first, last)
quick_sort(unsorted, first, pivot_index-1)
quick_sort(unsorted, pivot_index+1, last)
n = int(input())
_a = list(map(int, input().split()))
_b = list(map(int, input().split()))
minus_b = list(map(lambda x: -x, _b))
quick_sort(_a, 0, len(_a) - 1)
quick_sort(minus_b, 0, len(minus_b)-1)
_b = list(map(abs, minus_b))
print(sum(_a[i] * _b[i] for i in range(len(_a))))
- 데이터의 범위가 매우크기 때문에 단순한 알고리즘으로 풀리지 않을 것으로 예상됨
- sort()를 사용하여 풀어볼 것
- input 데이터의 갯수가 많기 때문에 이 시간을 줄여야 하고 아래와 같이 입력 받도록 한다.
import sys
n = int(sys.stdin.readline())
student = [sys.stdin.readline().split() for i in range(n)]
student.sort(key=lambda x: (-int(x[1]), int(x[2]), -int(x[3]), x[0]))
for i in range(n):
print(student[i][0])
import sys
n = int(input())
data = []
for _ in range(n):
data.append(sys.stdin.readline().split())
data.sort(key=lambda x: (-int(x[1]), int(x[2]), -int(x[3]), x[0]))
for d in data:
print(d[0])
댓글남기기