[알고리즘]정렬

버블정렬

일반적인 정렬
앞과 뒤를 비교해서 순차적으로 계속 비교해 나가는 모습이 거품이 일어나는 모습에 비유되어 버블정렬이다
O(n2)의 성능을 보인다

버블정렬 구현

이중for문으로 구현한다
for문 한 사이클 돌 때마다 제일 큰 수는 맨 뒤로 간다

 

python

	def bubbleSort(arr):
	for i in range(len(arr)):
	for j in range((len(arr) - i)-1):
	if arr[j] > arr[j + 1]:
	arr[j], arr[j + 1] = arr[j+1], arr[j]
	return arr
	arr = [5, 3, 2, 4, 1, 7]
	arr = bubbleSort(arr)
	print(arr)

view raw bubbleSort.py hosted with ❤ by GitHub

선택정렬

정렬순서상 가장 앞서는 것을 찾아서 왼쪽에 정렬
원래 정렬에 필요한 별도의 메모리 공간이 필요하지만
위치 교환이 좀 더 효율적이다
O(n2)의 성능을 보인다

선택정렬 구현

이중for문으로 구현한다
for문 한 사이클 돌 때마다 제일 작은 데이터부터 정렬 된다

 

python

	def selectionSort(arr):
	for i in range(len(arr)):
	maxIdx = i
	for j in range(i+1, len(arr)):
	if arr[j] < arr[maxIdx]:
	maxIdx = j
	arr[i], arr[maxIdx] = arr[maxIdx], arr[i]
	return arr
	arr = [5, 3, 2, 4, 7, 1]
	arr = selectionSort(arr)
	print(arr)

view raw selectionSort.py hosted with ❤ by GitHub

삽입정렬

정렬된 부분과 정렬이 되지않은 부분을 나눠서 정렬된 부분에 정렬이 안된 데이터를 하나씩 뽑아 정렬된 부분의 위치를 찾아 삽입하는 정렬
위치 교환이 아닌 정렬된 부분을 한 칸씩 뒤로 밀면서 삽입할 위치를 찾는다
O(n2)의 성능을 보인다

삽입정렬 구현

이중for문으로 구현한다
for문 한 사이클 돌 때마다 한 데이터의 삽입위치를 찾아 그 위치에 삽입되어 정렬된다

 

python

	def insertionSort(arr):
	i = 0
	j = 0
	for i in range(1, len(arr)):
	insData = arr[i]
	for j in range(i-1, -2, -1):
	if arr[j] > insData:
	arr[j+1] = arr[j]
	else:
	break
	arr[j+1] = insData
	return arr
	arr = [5, 3, 2, 4, 7, 1]
	arr = insertionSort(arr)
	print(arr)

view raw insertionSort.py hosted with ❤ by GitHub