정렬
- 버블 정렬
- 데이터의 인접 요소끼리 비교, swap 연산 수행하며 정렬
- 선택 정렬
- 대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하며 정렬
- 삽입 정렬
- 대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하며 정렬
- 퀵 정렬
- pivot 값을 선정해 해당 값을 기준으로 정렬
- 병합 정렬
- 이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬
- 기수 정렬
- 데이터의 자릿수를 바탕으로 비교해 데이터를 정렬
04-1 버블 정렬
- 버블 정렬은 두 인접한 데이터의 크기를 비교해 정렬하는 방법이다. 간단하게 구현할 순 있지만, 시간 복잡도는 O(n^2)으로 다른 정렬 알고리즘보다 속도가 느리다. 루프를 돌면서 인접한 데이터 간의 swap 연산으로 정렬한다.
[버블 정렬 과정]
1. 비교 연산이 필요한 루프 범위를 설정한다.
2. 인접한 데이터 값을 비교한다.
3. swap 조건에 부합하면 swap 연산을 수행한다.
4. 루프 범위가 끝날 때까지 2~3을 반복한다.
5. 정렬 영역을 설정한다. 다음 루프를 실행할 때는 이 영역을 제외한다.
6. 비교 대상이 없을 때까지 1~5를 반복한다.
- 만약 특정한 루프의 전체 영역에서 swap이 한 번도 발생하지 않았다면 그 영역 뒤에 있는 데이터가 모두 정렬됐다는 뜻이므로 프로세스를 종료해도 된다.
📌 문제 015) 수 정렬하기 1
시간 제한 2초, 브론즈 I, 백준 2750번
N개의 수가 주어졌을 때 이를 오름차순 정렬하는 프로그램을 작성하시오.
입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
5 # 수의 개수 5 2 3 4 1
출력
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
1 2 3 4 5
1단계 문제 분석
- 파이썬은 sort() 함수로 정렬이 가능하지만, 직접 정렬을 구현해보자.
- N의 최대 범위가 1,000으로 매우 작기 때문에 O(n^2) 시간 복잡도 알고리즘으로 풀 수 있다.
- 버블 정렬의 시간 복잡도가 O(n^2)이므로 버블 정렬 알고리즘으로 해결할 수 있다.
2단계 슈도 코드
N(정렬할 수 개수)
A(수 저장 리스트 선언 및 입력 데이터 저장)
for i를 0 ~ N-1만큼 반복:
for j를 0 ~ N-1-i만큼 반복:
현재 A 리스트의 값보다 1칸 오른쪽 리스트의 값이 더 작으면 두 수 바꾸기
A 리스트 출력3단계 코드 구현
N = int(input())
A = [0] * N
for i in range(N):
A[i] = int(input())
for i in range(N-1):
for j in range(N-1-i):
if A[j] > A[j+1]:
temp = A[j]
A[j] = A[j+1]
A[j+1] = temp
for i in range(N):
print(A[i])📌 문제 016) 버블 정렬 프로그램 1
시간 제한 2초, 골드 II, 백준 1377번
영식이는 버블 정렬 알고리즘을 다음과 같이 C++로 작성했다.
bool changed = false; for (int i=1; i<=N+1; i++) { changed = false; for (int j=1; j<=N-i; j++) { if (A[j] > A[j+1]) { changed = true; swap(A[j], A[j+1]); } } if (changed == false) { cout << i << '\n'; break; } }위 소스에서 N은 배열의 크기이고, A는 정렬해야 하는 배열이다. 배열은 A[1]부터 사용한다.
위와 같은 소스를 실행시켰을 때, 어떤 값이 출력되는지 구해보자.
입력
첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다.
5 # 배열의 크기 10 1 5 2 3
출력
정답을 출력한다.
3
1단계 문제 분석
- 버블 정렬의 swap이 한 번도 일어나지 않은 루프가 언제인지 알아내는 문제이다.
- 버블 정렬의 이중 for 문에서 안쪽 for문 전체를 돌 때 swap이 일어나지 않았다는 것은 이미 모든 데이터가 정렬됐다는 것을 의미한다. 이때는 프로세스를 바로 종료해 시간 복잡도를 줄일 수 있다.
- 이 문제는 N의 최대 범위가 500,000이므로 버블 정렬로 문제를 풀면 시간을 초과할 수 있다.
- 파이썬 sort() 함수의 시간 복잡도는 O(nlogn)이다.
- 각 데이터마다 정렬 전 index 값에서 정렬 후 index 값을 빼고 최댓값을 찾는다.
- 그리고 swap이 일어나지 않는 반복문이 한 번 더 실행되는 것을 감안해 최댓값에 1을 더한다.
2단계 슈도 코드
N(데이터 개수) A(데이터 리스트, 단 클래스를 데이터로 담는 리스트)
for N만큼 반복:
A 리스트 저장
A 리스트 정렬
for N만큼 반복:
A[i]의 정렬 전 index - 정렬 후 index 계산의 최댓값을 찾아 저장
최댓값 + 1을 정답으로 출력3단계 코드 구현
import sys
input = sys.stdin.readline
N = int(input())
A = []
for i in range(N):
A.append((int(input()), i)) # 정렬 기준을 고려하여 데이터, index 순서로 저장
Max = 0
sorted_A = sorted(A)
for i in range(N):
if Max < sorted_A[i][1] - i: # 정렬 전 index - 정렬 후 index 계산의 최댓값 저장
Max = sorted_A[i][1] - i
print(Max + 1)04-2 선택 정렬
- 선택 정렬은 대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법이다. 구현 방법이 복잡하고, 시간 복잡도도 O(n^2)으로 효율적이지 않아 코딩 테스트에서 많이 사용하지는 않는다. 간단하게만 알아보자.
[선택 정렬 과정]
1. 남은 정렬 부분에서 최솟값 또는 최댓값을 찾는다.
2. 남은 정렬 부분에서 가장 앞에 있는 데이터와 선택된 데이터를 swap한다.
3. 가장 앞에 있는 데이터의 위치를 변경해(index++) 남은 정렬 부분의 범위를 축소한다.
4. 전체 데이터 크기만큼 index가 커질 때까지, 즉 남은 정렬 부분이 없을 때까지 반복한다.
📌 문제 017) 내림차순으로 자릿수 정렬하기
시간 제한 2초, 실버 V, 백준 1427번
배열을 정렬하는 것은 쉽다. 수가 주어지면, 그 수의 각 자리수를 내림차순으로 정렬해보자.
입력
첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다.
2143
출력
첫째 줄에 자리수를 내림차순으로 정렬한 수를 출력한다.
4321
1단계 문제 분석
- 자연수를 받아 자릿수별로 정렬하는 문제이므로 먼저 숫자를 각 자릿수별로 나누는 작업이 필요하다.
- 파이썬에서는 input 데이터를 list로 변환하면 자동으로 각 자릿수로 나누어 리스트화해주기 때문에 변경이 매우 간편하다.
- list 변환을 사용하고 단순하게 배열 정렬을 하면 된다.
- sort() 함수 말고 N의 길이가 크지 않으므로 선택 정렬을 사용해보자.
- 내림차순 정렬이므로 최댓값을 찾아 기준이 되는 자리와 swap 하자.
2단계 슈도 코드
A(자릿수별로 구분해 저장한 리스트)
A 리스트 저장
for i를 A 리스트만큼 반복:
for j를 i+1 ~ A 리스트 길이만큼 반복:
현재 범위에서 Max 값 찾기
현재 i의 값과 Max값 중 Max값이 더 크면 swap 수행
A 리스트 출력3단계 코드 구현
import sys
print = sys.stdout.write
A = list(input())
for i in range(len(A)):
Max = i
for j in range(i+1, len(A)):
if A[j] > A[Max]: # 내림차순이므로 최댓값을 찾음
Max = j
if A[i] < A[Max]:
temp = A[i]
A[i] = A[Max]
A[Max] = temp
for i in range(len(A)):
print(A[i])