1. 파이썬의 알고리즘

1. 기본정렬

# 1.버블 정렬(Bubble sort)
* 정렬(sorting) : 어떤 데이터들이 주어졌을떄 이를 정해진 순서대로 나열하는것
* 정렬은 프로그램 작성시 빈번하게 필요로 함
* 다양한 알고리즘이 고안되었으며, 알고리즘 학습은 필수
* 다양한 정렬 알고리즘 이해를 총해서 동일한 문제에 대해 다양한 알고리즘이 고안될 수 있음을 이해하고, 각 알고리즘 간 성능 비교를 통해 알고리즘 성능 분석에 대해서도 이해할 수 있음
* 두 인접한 데이터를 비교해서 앞에 있는 데이터가 뒤에있는 데이터보다 자리를 바꾸는 정렬 알고리즘

# 1-1. 버블 정렬 알고리즘 구현하기
* 데이터가 네개일때(예: data_list=[1,9,3,2])
* 1차 로직 적용
     * 1과 9 비교, 자리바꿈없음 [1,9,3,2]
     * 9와 3 비교, 자리 바꿈 [1,3,9,2]
     * 9와 2 비교, 자리 바꿈 [1,3,2,9]
* 2차 로직적용
    * 1과 3 비교, 자리바꿈없음 [1,3,2,9]
    * 3과 2 비교, 자리 바꿈 [1,2,3,9]
    * 3과 9 비교, 자리바꿈없음 [1,2,3,9]
* 3차 로직적용
    * 1과 2 비교, 자리바꿈없음 [1,2,3,9]
    * 2과 3 비교, 자리바꿈없음 [1,2,3,9]
    * 3과 9 비교, 자리바꿈없음 [1,2,3,9]

> n개의 리스트가 있는 경우 최대 n-1번의 로직을 적용
> 로직을 1번 적용할때마다 가장 큰 숫자가 뒤에서부터 1개씩 결정됨
> 로직이 경우에 따라 일찍 끝날 수 있음. 따라서 로직을 적용할때 한번도 데이터가 교환된 적이 없다면 이미 정렬된 상태이므로 더 이상 로직을 반복 적용할 필요가 없음

def bubblesort(data):
    for index in range(len(data) -1):
        swap = False
        for index2 in range(len(data)- index -1):
          if data[index2] > data[index2 + 1]:
              data[index2], data[index2 + 1] = data[index2 + 1], data[index2]
              swap = True
        if swap == False:
          break
    return data
    
    
import random
data_list = random.sample(range(50), 25)
print(data_list)
print(bubblesort(data_list))
-->
[6, 39, 27, 42, 16, 22, 4, 7, 35, 18, 5, 33, 45, 13, 32, 44, 41, 28, 40, 34, 15, 47, 37, 11, 19]
[4, 5, 6, 7, 11, 13, 15, 16, 18, 19, 22, 27, 28, 32, 33, 34, 35, 37, 39, 40, 41, 42, 44, 45, 47]

2. 삽입정렬

# 삽입정렬은 두번째 인덱스부터 시작
# 두번째 원소부터 차례대로 앞에 있는 정렬된 부분과 비교하면서 자신의 자리를 찾아감
# 더 작은 값이 나오면 그 자리에 삽입하고, 나머지 원소들은 한칸씩 뒤로 밀림
# 리스트 끝까지 가면서 정렬을 완료함

### 1-1. 삽입 정렬 알고리즘 구현하기
* 데이터가 네개일때(예: data_list=9,3,2,5])
* 처음 실행하면 ket값은 9, 인덱스(0) -1은 0보다 작으므로 끝 : [9, 3, 2, 5]
* 두번째 실행 key 값은 3, 9보다 3이 작으므로 자리 바꾸고 끝 : [3, 9, 2, 5]
* 세번째 실행 key 값은 2, 9보다 2가 작으므로 자리 바꾸고,3 보다 2가 작으므로 자리 바꾸고 끝 : [2, 3, 9, 5]
* 네번째 실행 key 값은 5, 9보다 5가 작으므로 자리 바꾸고, 3보다 5가 크므로
 끝: [2,3,5,9]

def insertion_sort(data):
   for index in range(len(data) -1):
    for index2 in range(index + 1, 0, -1):
      if data[index2] < data[index2 - 1]:
          data[index2], data[index2 -1] = data[index2 -1], data[index2]
      else:
        break
        
import random
data_list = random.sample(range(50), 25)
print(data_list)
print(insertion_sort(data_list))
-->
[44, 30, 18, 47, 21, 49, 38, 29, 31, 35, 7, 10, 3, 23, 26, 4, 9, 22, 28, 11, 40, 46, 32, 39, 19]
None

# ** 3. 선택정렬(selection sort)
* 주어진 데이터 중, 최솟값을 찾음
* 해당 최소값을 데이터 맨앞에 위치한 값과 교체함
* 맨앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함

 

### 3-1. 선택정렬 알고리즘 구현하기
* 데이터가 두개일때 (예: datalist = [9,1])
    * data_list[0] > data_list[1] 이므로 data_list[0]값과 data_list[1]값을 교환
    * 데이터가 세개일때 (예: datalist = [9,1, 7])
      * 처음 실행하면 1, 9, 7이 됨
      * 주번째 실행하면 1 , 7, 9가 됨

    * 데이터가 네개일때 (예: datalist = [9,3,2,1])
      * 처음실행하면 1,3,2,9이 됨
      * 두번째 실행하면 1,2,3,9가 됨
      * 세번째 실행하면 변화없음  

def selection_sort(data):
    for stand in range(len(data) - 1):
        lowest = stand
        for index in range(stand + 1, len(data)):
            if data[lowest] > data[index]:
                lowest = index
        data[lowest], data[stand] = data[stand], data[lowest]
    return data


import random
data_list = random.sample(range(100), 20)
print(data_list)
print(selection_sort(data_list))
-->
[27, 52, 24, 11, 79, 40, 39, 78, 44, 76, 25, 91, 88, 92, 67, 36, 21, 60, 33, 3]
[3, 11, 21, 24, 25, 27, 33, 36, 39, 40, 44, 52, 60, 67, 76, 78, 79, 88, 91, 92]