정렬(sorting)이란?
키의 항목값의 대소 관계에 따라 데이터 집함을 일정한 순서로 바꾸어 늘어놓는 작업.
값이 작은 데이터를 앞쪽에 늘어놓는 것을 오름차순(ascending) 정렬이라고 하고, 그 반대를 내림차순(descending) 정렬이라고 한다.
대표적인 알고리즘 8가지를 소개할 예정.
(버블, 단순 선택, 단순 삽입, 셸, 퀵, 병합, 힙, 도수)
정렬 알고리즘의 안정성
안정적인(stable)한 알고리즘과,
그렇지 않은 알고리즘이 있다.
-
안정적인 정렬 알고리즘
값이 같은 원소의 순서가 정렬한 후에도 유지되는 것. -
안정적이지 않은 정렬 알고리즘
안정적이지 않은 건 원래의 순서가 유지된다는 보장이 없다.
내부 정렬과 외부 정렬
- 내부 정렬(internal sorting)
정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용하는 알고리즘. - 외부 정렬(external sorting)
정렬할 데이터가 많아서 하나의 배열에 저장할 수 없는 경우에 사용하는 알고리즘.
단순히 말하자면,
하나의 배열 안에서 해결할 수 있으면 내부 정렬, 불가하면 외부 정렬이다.
? 정렬 알고리즘의 핵심은 교환, 선택, 삽입.
버블 정렬(bubble sort)
두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘. 단순 교환 정렬이라고도 한다.
이웃한 원소를 비교하고,
필요하면 교환한다.
원소 수가 n인 배열에서 n-1번 비교, 교환을 하고 나면 가장 작은 원소인 1이 맨 앞으로 이동한다.
이러한 일련의 비교, 교환하는 과정을 패스(pass)라고 한다.
x[6]과 x[5]를 비교,
교환할 필요 있으면 교환,
x[5]와 x[4]를 비교,
...
첫번째 패스를 거치면, 가장 작은 원소가 앞에 오기때문에,
두번째 패스를 하면, 두번쨰로 작은 원소가 두번째에 온다.
패스를 한번 수행할 떄마다 정렬할 대상은 1개씩 줄어들기 때문에,
두번째 패스의 비교 횟수는 첫번째 패스보다 1개 적은,
n-2번이다.
패스를 k번 수행하면 k개 원소가 정렬되므로,
모든 정렬이 끝나려면 패스를 n-1번 수행해야한다.
수행하는 패스 횟수가 n번이 아니라 n-1번인 이유는,
n-1개의 원소의 정렬이 끝나면 마지막 원소는 이미 끝이기 때문이다.
? 버블 벙렬은 액체 속의 공기 방울이 가벼워서 보글보글 올라오는 모습에 착안해서 붙인 이름이다.
버블 정렬 프로그램
음...
뭐...
def bubble_sort(a: MutableSequence) -> None:
for j in range(n-1):
for i in range(len(a)+1):
if a[i] > a[i-1] :
a[i], a[i-1] = a[i-1], a[i]
여기까지 쓰고 깨달은건데
앞부분을 설정하면 뒤에 비교하는 식을 쓸때
이미 한번 정렬을 끝내고 났기때문에
정렬하는 횟수를 줄이는 부분을 구현해야...
하는데...
for j in range(n-1, i, -1):
if a[j-1] > a[j]:
a[j -1], a[j] = a[j], a[j-1]범위 설정이 정말 예술적이야..
앞에 큰수, 뒤에 작은 수 두고 -1로 역순으로 가기때문에
10, 9, 8순으로 출력시켰어..!
이 자식 진짜야..!!!
천재적이야..!!
아무튼 그래서 비교 횟수는
첫번째 패스에서 n-1번, 두번째 패스에서 n-2번...
이라, 합계는,
(n-1) + (n-1) + .... + 1 = n(n-1)/2
인데, 원소값에 영향을 받으므로 평균값은 그의 절반으로 가정한다.
알고리즘의 개선1
만약 패스를 하다가,
원소 교환 횟수가 0이라면 이미 정렬을 마친 상태이므로,
거기서 중단 시킨다면 비교를 더 하지 않는다.
def bubble_sort(a: MutableSequence) -> None:
cnt = 0
n = len(a)
for i in range(n-1):
for j in range(n-1, i, -1):
if a[j-1] > a[j]:
a[j -1], a[j] = a[j], a[j-1]
cnt += 1
if cnt == 0:
break
cnt = 0흠... cnt를 쟤는 ..그러니까
첫 for문 바로 아래에 뒀는데 뭐? 비슷하지않을까..
그것빼곤 똑같다.
알고리즘의 개선2
앞부분 정렬을 하다가,
만약 특정한 원소 이후에 교환을 하지 않는다면,
앞 부분은 이미 정렬이 완료된 상태일 것이다.
그러면 그 원소 이후부터 비교, 교환하면 된다.
아니 말은 쉽지 이 사람아
이것만 하고 쉬는 시간 가져야지 --진짜
너무 모르겠어서 한번 봤는데
하... 이걸 어떻게 생각해내냐
비교했던 마지막 인덱스 번호를 저장함
만약 다 끝내고 나면, 마지막 교환했던 인덱스 번호를 갖고 있음.
그 마지막 교환했던 인덱스 번호로, 범위 설정을 다시 함.
for로 되어있는 범위 설정을,
아예 k라는.. 인덱스 저장하는 범위로..
코드를 보시죠
n = len(a)
k = 0
while k < n-1 :
last = n-1
for i in range(n-1,k,-1):
if a[i-1] > a[i]:
a[i-1], a[i] = a[i], a[i-1]
last = i
k = last 내가 앞 이론 보고 썼을 때는
last를 다시 n-1로 초기화해주는 과정을 빼먹었었다...그렇군.
셰이커 정렬 알아보기
만약 가장 큰 원소가 맨 앞에 있고,
나머지는 정렬되어있다면,
시간이 오래 걸릴 것이다.
그래서
-
홀수 패스에서는 가장 작은 원소를 맨 앞으로 이동
-
짝수 패스에서는 가장 큰 원소를 맨뒤로 이동
으로 스캔 방향을 번갈아 바꾸어보자.
이렇게 버블 정렬을 개선한 알고리즘을
셰이커 정렬(shaker sort)이라고 하며,
양방향 버블 정렬, 칵테일 정렬,
칵테일 셰이커 정렬이라고도 한다.
...
아니 무슨 어?
홀수일땐 저거 실행하고 짝수일땐 저거 실행해?
패스 횟수를 계산해서,
패스가 홀수일때는 원래 수식을 하고,
패스가 짝수일떄는 반대로 하는 수식으로...
def shaker_sort(a: MutableSequence)-> None:
pass = 0
n = len(a)
for i in range(n-1):
if pass % 2:
for j in range(n-1, i, -1):
if a[j-1] > a[j]:
a[j -1], a[j] = a[j], a[j-1]
pass += 1
else :
for i in range(i, n-1, 1):
if a[i]> a[i-1]:
a[i], a[i-1] = a[i-1], a[i]
pass +=1
책에서는...
left와 right를 정의하고,
last를 만들어서,
아예 범위를 손쉽게...
이건 마지막 개선 알고리즘2도 섞었군
어떻게 했냐면
그냥
while문에
홀수와 짝수는 번갈아할테니까
for문으로 순서대로 집어넣었어.
그다음 last로 하는 알고리즘을 그대로
대입해서 넣었군.
나야 뭐 pass 숫자가 중간에 바뀌지는 않겠지만,
last를 넣으려면
어차피 range안의 값을 변수화 시켜야하기때문에
그 부분을 고치면 정답 코드가 될거같다.
그리고 표현이 되게 사람이 해석하기 쉽게 설정해놨어.
left와 right라 어디에서 어디로 가는지 알기 쉽다.
산술 연산에 사용하는 내장 함수
-
abs()
x의 절댓값을 반환 -
bool() x의 논리값을 반환
-
complex(real, imag)
rear + imag * 1j인 복소수를 반환하거나,
문자열 또는 수를 복소수로 변환한 값을 반환합니다. -
divmod(a,b)
a를 b로 나누었을 때의 몫과 나머지로 구성된 튜플을 반환합니다. -
hex(x)
x의 16진수 문자열을 반환합니다. -
int(x,base)
int형 정수를 반환하되, base는 0~36범위 내 진수를 나타냅니다. -
max(), min()
-
oct()
8진수 문자열을 반환합니다. -
pow(x, y, z)
x의 y의 제곱인 x ** y를 반홥합니다.
z값을 입력하면 x의 y제곱을 z로 나누었을 때의 나머지를 반홥합니다. -
round (n, ndigits)
n의 소수부를 ndigits 자릿수가 되도록 반올림한 값을 반환합니다. (3을 넣으면 소수점 아래 3자리 보존해서 반올림) -
sum (x, start)
처음부터 끝까지 순서대로 더한 총합에 start값을 더하여 반환합니다.
단순 선택 정렬(straight selection sort)
가장 작은 원소부터 선택해,
알맞은 위치로 옮기는 작업을 반복하며 정렬하는 알고리즘.
아직 정렬하지 않은 범위에서
값이 가장 작은 원소를 선택하고,
아직 정렬하지 않은 부분의 맨 앞 원소와 교환하는 작업을 반복한다.
- 아직 정렬하지 않은 부분에서, 값이 가장 작은 원소 a[min]을 선택한다.
- a[min]과 아직 정렬하지 않은 부분에서 맨 앞에 있는 원소를 교환한다.
for i in range(n-1):
min
a[i]와 a[min]의 값을 교환한다.
해보겠다.
n = len(a)- 1
min = a[0]
for i in range(n-1):
for j in range(i,n-1):
if a[j] > a[j+1]:
min = j+1
a[i] = a[min]헷갈려..
잘 안 헷갈리는 법은 뭐지..
일단...
총 n-1번 확인할거다
그걸 여태 정렬되지 않은 범위 내에서 할건데
i번째부터 뒷부분까지 할거고
만약 비교해서 크다면 작은쪽을 min에 저장해서
끝까지 돌린 뒤
그 min의 값을 i번째에 넣겠다...
...
정답 코드 확인.
n = len(a)
for i in range(n-1):
min = i
for j in range(i +1,n):
if a[j] < a[min]:
min = j
a[i], a[min] = a[min], a[i]n을 두번 빼고 말았고...
정렬할 부분에서 가장 작은 원소의 인덱스를 i로 해놓아야,
나중에 본래의 인덱스와 치환할때 제대로 호출 할수 있음.
내가 하는 방식은 값을 덮어씌울거고,
또 가장 작은 값 기준으로 비교하지 않고 버블처럼 했기때문에,
...
근데 버블처럼 해도? 되지않나?
연산 횟수가 작?은 것 같지도 않은데.
min을 리셋하지 않았긴 한데...
아!
그냥 min을 인덱스로만 저장했기때문에
버블 형식으로 비교하면 가장 작은 값이 저장되는게 아니라,
그냥 순차적으로 했을 때 더 작은 쪽이 나올때마다 갱신된다.
범위 설정을 할때는 몇번째에서 시작하고,
어디에서 어디까지 하는지 문장으로 생각해보는게 좋을 거같고.
range는 마지막은 출력 안 되고,
인덱스는 0부터 시작하는 거 유념하고.
빼먹은 로직은,
- 찾은 값과 가장 앞 원소를 '교환'한다.
- 가장 작은 값을 찾고, 가장 작은 값을 기억해두고, '그 모든 값이 가장 작은 값보다 작은 지' 비교한다.
정도..
아무튼,
단순 선택 정렬 알고리즘의 원솟값을 비교하는 횟수는
(n**2-n)/2번 이다.
그러나 이 방법은,
값이 같은 원소가 있을 경우,
중복이기때문에 순서를 바꿀 필요가 없는데,
위치에 따라 정렬 중 둘의 순서가 바뀌어 정렬 될 수 있다.
그래서 안정적이지 않은 정렬 알고리즘이다.
단순 삽입 정렬(straight insertion sort)
보고 있는 원소에서,
정렬하고 있는 앞쪽에서,
알맞은 위치를 찾아 삽입하며 정렬하는 알고리즘이다.
단순 선택 정렬과 비슷해보여도,
가장 작은 값을 구태여 찾지 않는다.
단순 정렬 알아보기
확인하는 원소에서 확인해보고,
맨 알맞은 위치에 삽입한 뒤,
그 뒤의 숫자들은 뒤로 보낸다...
...
이 작업을 반복한다.
아직 정렬 되지 않은 부분의 맨 앞 원소를 정렬된 부분의 알맞은 위치에 삽입합니다.
알고리즘의 개요는 다음과 같다.
for i in range(1,n):
tmp <- a[i]를 넣는다.
tmp를 a[0], ... a[i-1] 알맞은 위치에 삽입한다.난 삽입하는 게 좀? 헷갈리긴 하더라.
알맞은 위치에 삽입하는 과정을 보겠다.
왼쪽에 이웃한 원소가, 선택한 원소보다 크면,
그 값을 오른쪽에 있는 원소에 대입하고...
..
아 뭐 간단히 말하자면,
삽입하고자 하는 값을 기억해둠.
(3)
그 값과 왼쪽을 비교함.
왼쪽이 크다? 다음 인덱스로 옮겨줌.
(3)
(6) (7) > (3)
(6) (7) (7)
그러다 왼쪽 값이 더 작은 지점이 나올 거임.
(3)
(2) (6) (6) (7) ...
그러면 그 자리에 기억해둔 값을 삽입함.
(2) (3) (6) (7)
...
뭐지?
인덱스 쭉 높...이고 있지않아??
쩝..
종료 조건은 두 가지.
- 정렬된 배열의 왼쪽 끝에 도달한 경우.
- tmp보다 작거나 키값이 작은 원소 a[j-1]을 발견할 경우.
계속 조건은 두가지다.
드모르간의 법칙을 적용한다.
(참 잘 쓴 책이야!)
- j가 0보다 큰 경우
- a[j-1]의 값이 tmp보다 큰 경우.
? 드모르간의 법칙
- x and y = not(not x or not y)
- x or y = not(not x and not y)
1부터 n까지 ... 반복하겠습니다! 한개씩 뽑는걸 i라고 할게요.
현재 주목하고 있는 원소는 tmp,a[i]!
우리가 볼 범위는, 그 앞! range(i,0,-1) 1개씩 뽑는걸 j라고 할게요.
a[j]는 a[i]보다 큰가요?
크다면 a[j] = a[j+1] 해주세요.
작은가요?
그렇다면 멈출게요.
조건문이 끝나면, a[j]에 a[i]를 넣을게요.
아니 여기에 드모르간의 법칙을 어떻게 넣어요 참나
def insertion_sort(a: MutableSequence) -> None:
n = len(a)
for i in range(1,n):
j = i
tmp = a[i]
while j > 0 and a[j -1] > tmp:
a[j] = a[j-1]
j -= 1
a[j] = tmp
흠...
-
현재 위치가 1보다 크고, 그 왼쪽에 있는게 현재 수보다 작다면 값을 옮깁니다.
그 바로 왼쪽으로 이동합니다.
이걸 반복합니다. -
전부 옮기고 나면, 그 자리에 멈춰있습니다.
그 자리에 현재 값을 넣어줍니다.
이것을 나머지 범위에서도 진행합니다.
내가 한 것의 문제점
:챗 지피티 협찬
range(i, 0, -1)을 통해 선택된 j의 범위는 i부터 1까지 감소하는데, 이는 a[j]를 확인하는 범위를 정렬된 부분의 시작부터 끝까지로 설정하는 것이 아니라 정렬된 부분의 끝부터 시작으로 설정하고 있습니다. 정렬된 부분은 a[0]에서 a[i-1]까지인데, 여기서 a[0]이 가장 작은 값이므로, a[j]와 a[i]를 비교할 때는 a[j]가 더 큰지 여부를 확인해야 합니다. 따라서 range(i-1, -1, -1)로 수정해야 합니다.
두 번째로, a[j]와 a[i]를 비교하여 크다면 a[j]를 a[j+1]로 덮어쓰고 작다면 멈추는 로직이 있습니다. 그러나 이 구현에서는 작을 때 멈추는 부분이 구체적으로 어떻게 처리되는지 명시되어 있지 않습니다. 작을 때 멈추는 부분에 대한 처리가 필요합니다.
간단히 말하자면..
1. 맨 뒤에서부터 시작하고있는데요!
2. 작다면 멈춘다.
음...뭐 그냥? break 처리하고
하면 안 되는 건가?
for i in range(1,n):
tmp = a[i]
for j in range(i-1,-1,-1):
if a[j] > a[i]:
a[j] = a[j+1]
else:
break
a[j] = tmp이 코드도 되긴 된다네요
구현의 효율성은 일반적으로 큰 차이가 없고,
정답 코드가 더 직관적으로 보인다... 라고.
동의..합니다.
내가 만약 정답 코드를 떠올리려고 한다면...
for 문 대신 while을 쓰고,
j로 종료 조건을 주며... 정도?
아무튼..
이 알고리즘은 서로 떨어져있는 원소를 교환하지 않으므로, 안정적이라고 할 수 있다.
원소의 비교 횟수와 교환 횟수는 모두 n**2//2번이다.
단순 삽입 정렬은 셔틀 정렬(shuttle sort)이라고도 한다.
여태까지의 단순 정렬의 시간 복잡도는
모두 O(n**2)로 좋지 않다.
개선 방법을 적용한 정렬 알고리즘을 알아보자.
