기초 알고리즘 [정렬]

정렬 

arr = [3,1,4,5,2] 
arr.sort()  # 오름차순 정렬 
print(arr) #[1,2,3,4,5]

arr.sort(reverse = True) #내림차순 정렬
print(arr) #[5,4,3,2,1]

 

정렬로직에는 선택정렬, 삽입정렬, 버블정렬등이 있다. 이 로직들은 크게 복잡하지 않아 쉽게 배울 수 있다는 장점이 있찌만, 너무 느리기 때문에 실제로 사용하기는 어렵다.

---

선택정렬

: 선택정렬은 우리가 앞에서 배운 최대값, 최소값을 찾는 로직과 두 값을 바꿔주는 로직을 혼합하여 구현하는 로직이다

 

3 1 4 5 2  #처음 주어진 리스트 

1 3 4 5 2  # 최소값 1과 맨 앞의 수인 3과 교환 

1 2 4 5 3  #첫번째를 제외한 최소값 2와 두번째 수인 3과 교환 

1 2 3 5 4 #두번째를 제외한 최소값 3와 세번째 수인 4와 교환 

1 2 3 4 5  #세번째를 제외한 최소값 4와 네번째 수인 5를 교환 

 

arr = [ 3,1,4,5,2] 

def selection_sort(arr) :
	n = len(arr) #리스트 길이 확인
    for i in range(n) :
    	min_idx = i 
        for j in range(i+1 , n) : 
        	if arr[j] < arr[min_idx] : 
            	min_idx = j 
        arr[i] , arr[min_idx] = arr[min_idx] , arr[i] 
   return arr

 

 

거품정렬(버블정렬)

: 앞에서 두 수를 비교해서 큰 수를 뒤로 보내는 것을 반복하는 방법 

 

3 1 4 5 2  #처음 주어진 리스트 

1 3 4 5 2  # 3과1을 비교해서 큰 수를 뒤로 보냄 

1 3 4 5 2  #3과4는 정렬이 되어 있으므로 넘어감

1 3 4 5 2 #4와 5도 정렬이 되어 있으므로 넘어감 

1 3 4 2 5 #2와 5의 자리를 바꿔줌 

1 3 2 4 5 #4와 2의 자리를 바꿔줌

1 2 3 4 5 #3과 2의 자리를 바꿔줌

def bubble_sort(arr) :
	n = len(arr) 
    for i in range(n) :
    	for j in range(n-i-1) :
        	if arr[j+1] < arr[j] :
            	arr[j],arr[j+1] = arr[j+1],arr[j]
    return arr

삽입 정렬

: 새로운 리스트에 기존 리스트 값을 위치에 맞게 넣는 방식으로 진행 

 

3 1 4 5 2  #처음 주어진 리스트 

3 #기존 리스트에서 첫번째 값을 꺼내여 새로운 리스트에 넣음 

1 3 #1을 꺼내어 3과 비교하여 정렬 

1 3 4 #위의 리스트에서 4의 위치에 맞게 삽입함 

1 3 4 5 #위의 리스트에서 5의 위치에 맞게 삽입함

1 2 3 4 5 #위의 리스트에서 2의 위치에 맞게 삽입함

 

def insertion_sort(arr) : 
	new_arr = [arr[0]] 
    for i in range(1,len(arr)) :
    	j = 0
    	while j < i and arr[j] < arr[i] :
        	j+=1
        new_arr.insert(j,arr[i]) 
    return new_arr