정렬
-
대부분의 정렬 알고리즘은 ‘key value’를 비교하는 비교 연산과 자료의 위치를 바꾸는 이동 연산이 있음
- 이동 횟수와 비교 횟수를 통해 효율성을 판단
-
컴퓨터 메모리 내부에서 정렬하는 ‘내부 정렬 알고리즘’과 보조기억장치에서 정렬하는 ‘외부 정렬 알고리즘’이 존재
- 내부 정렬 알고리즘
- 외부 정렬 알고리즘
- 내부 정렬 알고리즘
-
대부분 O(n^2) ~ O(nlogn) 사이의 복잡도를 가지고 있음
정렬 알고리즘의 분류
- 기본 정렬 알고리즘 : O(n^2)
- 효율적 정렬 알고리즘 : O(nlogn)
- 특수한 조건을 만족했을 때 O(n)이 되는 알고리즘
기본적인 정렬 알고리즘
- 평균적으로 O(n^2)의 시간이 소요되는 정렬 알고리즘
- 선택 정렬 (Selection Sort)
- 버블 정렬 (Bubble Sort)
- 삽입 정렬 (Insertion Sort)
선택 정렬
-
정렬 되지 않은 데이터들에 대해 가장 큰 데이터를 찾아 가장 뒤의 데이터와 교환해 나가는 방식
-
정렬되지 않은 전체 데이터 중에서 해당 위치에 맞는 데이터를 선택하여 위치를 교환
-
각 루프마다
- 최대 원소를 찾는다
- 최대 원소와 맨 오른쪽 원소를 교환한다.
- 맨 오른쪽 원소를 제외한다.
-
위의 루프를 하나의 원소만 남을 때 까지 반복한다.
코드 구현
import sys
def Selection_Sort(arr,n): #가장 큰 요소를 찾고 가장 마지막에 놓는다.
target = arr[0]
target_loc = 0
#가장 큰 수 찾기
for i in range(1,n):
if target < arr[i]:
target = arr[i]
target_loc = i
#가장 큰 수와 마지막 요소의 값을 교환
if target_loc != n-1:
arr[target_loc],arr[n-1] = arr[n-1],arr[target_loc]
arr = [] # 빈 배열 생성
n = int(input("요소의 갯 수: "))
for i in range(n):
num = int(input())
arr.append(num)
for j in range(n):
if(n-j != 0):
print(n-j)
Selection_Sort(arr,n-j)
print(arr)수행시간
가장 큰 수를 n번 찾고 가장 큰 수와 가장 마지막 요소의 값을 교환하는 것을 n번 반복 해야하기 때문에
O(n^2)의 시간 복잡도를 갖는다.
버블 정렬
-
서로 이웃한 데이터들을 비교하며 가장 큰 데이터를 가장 뒤로 보내며 정렬
-
1 회전을 수행하고 나면 가장 큰 데이터가 맨 뒤로 이동하기 때문에 2 회전에서는 맨 끝에 있는 데이터는 정렬에서 제외 됨
- 즉, 정렬을 1회전 수행 할 때 마다 정렬에서 제외되는 데이터가 하나씩 늘어남
코드 구현
import sys
def BubbleSort(arr,n):
for i in range(n-1):# n - 2 번 탐색
for k in range((n-1)-i): #1회 반복 후 마지막 제외, n-1번 비교
# 비교 후 큰 값과 작은 값 교환
if arr[k] > arr[k+1]:
arr[k+1],arr[k] = arr[k],arr[k+1]
arr = []
n = int(input("요소의 갯 수 : "))
for i in range(n):
arr.append(int(input()))
if n >= 2:
BubbleSort(arr,n)
print(arr)- 만약 n = 4 일 때
- 총 3번 ( n - 1이어야 0,1,2 총 3번 검사 진행 )을 전체 검사
- 총 (n - 1) - i번의 비교 연산이 필요하다
- Loop를 한번 돌 때마다 마지막의 가장 큰 값이 정렬 되기 때문에 해당 자리를 제외시킨다.
수행 시간
시간 복잡도가 최선일 때 : O(n)
시간 복잡도가 최악 일 때 : O(n^2)
삽입 정렬
-
아직 정렬되지 않은 임의의 데이터를 이미 정렬 된 부분의 적절한 위치에 삽입해 가며 정렬하는 방식
-
선택된 ’키 값’을 앞 쪽 데이터들의 키 값과 비교하여 자신의 위치를 찾아 삽입하여 정렬
-
데이터 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입
-
삽입 정렬에서 처음 ‘키 값’은 두 번째 데이터로 부터 시작
-
대상 자료가 일부 정렬되어 있을 때 유리한 정렬 방식
삽입 정렬 알고리즘
-
쪼개고 합친다!!
-
각 루프마다 왼쪽에 제외하는 원소의 영역을 설정
-
나머지 array 중 해당하는 원소를 제외하는 영역에 정렬이 유지되도록 삽입
-
배열 A[1]만 놓고 보면
- 정렬이 되어있음
-
배열 A[1….k] 까지 정렬되어 있다면
- 행의 삽입에 의해 A[1….K + 1]까지 정렬된다.
import sys
def InsertSort(arr):
for i in range(1,): #index 1 부터 마지막 까지 삽입해야 함
for j in range(i,0,-1): #key값 기준 좌측 배열을 정렬 시켜야 함
if arr[j] < arr[j-1]:
arr[j],arr[j-1] = arr[j-1],arr[j]
arr = []
n = int(input("원소의 갯 수: "))
for i in range(n):
arr.append(int(input()))
