TIL - EP 26 - 29
2023.01.21
1. 정렬 알고리즘
시간복잡도는 같으면서 성능은 다른 정렬 알고리즘 3가지.
-
왼쪽, 오른쪽만 보면서 정렬하는 버블정렬
-
무질서한 순서로 놓인 1부터 9까지 9개의 숫자들을 오름차순 정렬 한다고 생각해보자.
1 , 3 , 4 , 2 , 8 , 6 , 9 , 7 , 5
버블정렬은 맨 왼쪽 또는 오른쪽부터 인접합 두 개의 수를 비교하여 큰 숫자를 오른쪽으로 넘긴다.
1)
(1 , 3) , 4 , 2 , 8 , 6 , 9 , 7 , 5
2)1 , (3 , 4) , 2 , 8 , 6 , 9 , 7 , 5
3)1 , 3 , (4 , 2) , 8 , 6 , 9 , 7 , 5
4)1 , 3 , (2 , 4) , 8 , 6 , 9 , 7 , 5
5)1 , 3 , 2 , (4 , 8) , 6 , 9 , 7 , 5...이런 순서로 맨 끝까지 한 바퀴를 돌면 1 사이클 이라고 한다. 1사이클이 끝나면 9가 맨 오른쪽에 위치할 것이다. 두번째 사이클을 할 때는 맨 오른쪽의 9를 제외할 수 있다.
-
버블정렬의 시간복잡도는 O(n^2)
n개의 숫자가 있을 때, 첫 1 사이클의 비교 횟수는 n-1번이다.
두 번째 사이클에서 정렬된 수를 제외하면 n-1개의 숫자가 남고 n-2회 비교한다.
따라서, 총 비교 횟수 = (n-1) + (n-2) + (n-3) ... + 1 = n(n-1)/2시간복잡도가 O(n^2) 인 알고리즘은 썩 좋지 않다. 따라서 버블 정렬은 잘 쓰지 않는다.
-
-
하나를 콕 집어 가며 정렬하는 선택 정렬
-
선택정렬은 비교 대상인 숫자를 한 사이클 탐색하며 가장 최소 또는 최대인 수의 위치를 기억하고, 사이클의 마지막에 가장 큰 수를 맨 오른쪽 또는 가장 작은 수를 맨 왼쪽으로 자리를 바꾼다. 다음 사이클에서는 이전 사이클에서 이동한 수를 제외하고 탐색한다.
-
선택정렬의 시간복잡도는 마찬가지로 O(n^2) 이다. 하지만 자리를 바꾸는 연산이 버블정렬에서는 1사이클당 최대 n-1번 까지 일어날 수 있는 반면, 선택정렬에서는 1사이클당 최대 1회만 일어나기 때문에 훨씬 효율적이라고 할 수 있다.
-
-
앞에 있는 데이터를 보면서 배치하는 삽입 정렬
-
삽입정렬은 1번 자리의 데이터부터 시작해 그 앞의 자리를 본다.
8 , 6 , 2 , 1 , 3 , 4 , 9 , 5 , 7
이 있을 경우 6부터 앞의 8과 비교를 하고 6이 8보다 작으니 8 앞쪽으로 6을 밀어 넣는다.
6 , 8 , 2 , 1 , 3 , 4 , 9 , 5 , 7
그 다음은 2번 자리에 있는 숫자 2를 보고 8과 비교한다. 마찬가지로 2가 8보다 작으니 8앞으로 2를 밀어넣고 다이 그 앞의 6과 비교한다.
6 , 8 , 2 , 1 , 3 , 4 , 9 , 5 , 7
6 , 2 , 8 , 1 , 3 , 4 , 9 , 5 , 7
2 , 6 , 8 , 1 , 3 , 4 , 9 , 5 , 7처음부터 오름차순으로 정렬이 되어있을 경우 n-1 사이클에 삽입 없이 정렬이 끝나게 되지만 내림차순으로 정렬된 데이터를 삽입정렬 할 경우 최악의 사태가 발생한다. 또 비교할 데이터의 양이 많아질수록 (n이 커질수록) 비효율이 증가하게 된다.
-
이 최악의 경우 삽입정렬의 시간복잡도는 O(n^2) 이다.
-
1 - 1 시간복잡도가 같더라도 실제 수행 속도는 다를 수 있다.
위에서 본 것 처럼 시간복잡도가 같은 알고리즘이라 하더라도 데이터의 양과 원본 데이터의 상태에 따라 연산의 효율이 달라질 수 있다.
2. 자료구조 스택 vs 큐
-
스택(stack)은 "쌓기"의 개념이다. 팬케이크를 생각해보자. 여러장의 팬캐이크를 굽고 쌓아서 보관해두는 상황에서 가장 처음에 놓인 팬케이크를 가장 나중에 먹게 되고, 가장 나중에 쌓은 팬케이크는 맨 위에 위치하기 때문에 맨 처음 먹게 된다. 이처럼 위로 데이터를 쌓고 위에서부터 데이터를 처리하는 것을 스택이라고 한다.
- 웹 브라우저에는 뒤로가기 버튼이 있다. 우리가 이동하면서 본 페이지들이 차곡차곡 쌓여서 (stack) 뒤로가기 버튼을 누르면 한 칸 아래 있는 페이지가 다시 보이게 된다.
-
큐(queue)는 스택과 반대로 먼저 놓인 팬케이크를 먼저 먹게 되는 상황이다. 먼저 줄을 서있는 사람이 먼저 입장하는 것 처럼, 큐는 위로 데이터를 쌓고 아래에서부터 데이터를 처리하는 것이다.
- 쇼핑몰의 주문 처리 시스템은 먼저 들어온 주문을 먼저 처리한다.
