스파르타코딩 - 알고리즘 강의 3 주차 (ft.정렬)

버블정렬

• 바로 앞에 배열과 비교

  input = [4, 6, 2, 9, 1]
  
  def bubble_sort(array):
      n = len(array)
      for i in range(n - 1): # 배열의 크기 - 1  까지
          for j in range(n - i - 1): # 0123,012,01,0 순으로 검사함
              if array[j] > array[j + 1]: # 바로 앞에 배열과 비교해서 변경
                  # 파이썬 치환 문법은 a, b = b, a
                  array[j], array[j + 1] = array[j + 1], array[j] 
  
      return array
  
  bubble_sort(input)
  print(input)  # [1, 2, 4, 6, 9] 가 되어야 합니다!
  
  print("정답 = [1, 2, 4, 6, 9] / 현재 풀이 값 = ",bubble_sort([4, 6, 2, 9, 1]))
  print("정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ",bubble_sort([3,-1,17,9]))
  print("정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ",bubble_sort([100,56,-3,32,44]))

선택정렬

• 최소값을 찾아 변경 : array(min_index)

  input = [4, 6, 2, 9, 1]
  
  def selection_sort(array):
      n = len(array)
      for i in range(n - 1):
          min_index = i
          for j in range(n - i): # 01234, 1234, 234, 34 순으로 검사 (ft.i + j)
              if array[i + j] < array[min_index]:
                  min_index = i + j
  
          array[i], array[min_index] = array[min_index], array[i]
  
      return array
  
  # 버블 정렬하고 다른 건 바로 "최솟값"을 찾아 변경하는 것입니다.
  # 따라서, min_index 라는 변수를 통해 각각의 인덱스들과 비교합니다.
  # 그리고 내부의 반복문이 끝나면, 최소 값의 인덱스와 i의 값들을 교체해주면 됩니다!
  
  selection_sort(input)
  print(input) # [1, 2, 4, 6, 9] 가 되어야 합니다!
  
  print("정답 = [1, 2, 4, 6, 9] / 현재 풀이 값 = ",selection_sort([4, 6, 2, 9, 1]))
  print("정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ",selection_sort([3,-1,17,9]))
  print("정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ",selection_sort([100,56,-3,32,44]))

삽입정렬

• 1부터 n까지

  input = [4, 6, 2, 9, 1]
  
  def insertion_sort(array):
      n = len(array)
      for i in range(1, n):
          for j in range(i): # 1, 21, 321, 4321 순임 (ft. i - j)
              if array[i - j - 1] > array[i - j]:
                  array[i - j - 1], array[i - j] = array[i - j], array[i - j - 1]
              else:
                  break
  
      return  array
  
  insertion_sort(input)
  print(input) # [1, 2, 4, 6, 9] 가 되어야 합니다!
  
  print("정답 = [4, 5, 7, 7, 8] / 현재 풀이 값 = ",insertion_sort([5,8,4,7,7]))
  print("정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ",insertion_sort([3,-1,17,9]))
  print("정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ",insertion_sort([100,56,-3,32,44]))

keyword

# 버블정렬 - 바로 앞에 것과 비교
n = array
* for i in range(n - 1):
* 	for j in range(n - i - 1):
*			if array[j] > array[j + 1]:

* i 의 범위 : n-i
* j 의 범위 : n-i-1
* 조건 : arr[j] > arr[j+1}

# 선택정렬 - 최소값을 찾아 비교
n = array
* for i in range(n - 1):
* 	for j in range(n - i):
*			if array[i + j] < array[min_index]:
					min_index = i + j

* i 의 범위 : n-1
* j 의 범위 : n-i
* 조건 : arr[i+j] < arr[min_idx]

# 삽입정렬 - 1부터 시작
n = array
* for i in range(1, n):
* 	for j in range(i):
*			if array[i - j - 1] > array[i - j]:

* i 의 범위 : 1, n
* j 의 범위 : i
* 조건 : arr[i-j-1] > arr[i-j]

1번째 : [4,6,2,9,1]
         ← 비교!
2번째 : [4,6,2,9,1]
         ← ← 비교!
3번째 : [2,4,6,9,1]
         ← ← ← 비교!
4번째 : [2,4,6,9,1]
         ← ← ← ← 비교!

병합정렬

• 재귀함수 활용 모두분해해서 합치면서 정렬ㄹㄹㄹ

  array = [5, 3, 2, 1, 6, 8, 7, 4]
  
  def merge_sort(array): # 최소한의 좌우 배열로 나누며 재귀한다.
      if len(array) <= 1:
          return array
      mid = len(array) // 2
      left_array = array[:mid]
      right_array = array[mid:]
      return merge(merge_sort(left_array), merge_sort(right_array))
  
  def merge(array1, array2):  # 왼쪽과 오른쪽을 병합한다.
      result = []
      array1_index = 0
      array2_index = 0
      while array1_index < len(array1) and array2_index < len(array2):
          if array1[array1_index] < array2[array2_index]:
              result.append(array1[array1_index])
              array1_index += 1
          else:
              result.append(array2[array2_index])
              array2_index += 1
  
      if array1_index == len(array1): 
          while array2_index < len(array2):
              result.append(array2[array2_index])
              array2_index += 1
  
      if array2_index == len(array2):
          while array1_index < len(array1):
              result.append(array1[array1_index])
              array1_index += 1
  
      return result
  
  print(merge_sort(array))  # [1, 2, 3, 4, 5, 6, 7, 8] 가 되어야 합니다!
  
  print("정답 = [-7, -1, 5, 6, 9, 10, 11, 40] / 현재 풀이 값 = ", merge_sort([-7, -1, 9, 40, 5, 6, 10, 11]))
  print("정답 = [-1, 2, 3, 5, 10, 40, 78, 100] / 현재 풀이 값 = ", merge_sort([-1, 2, 3, 5, 40, 10, 78, 100]))
  print("정답 = [-1, -1, 0, 1, 6, 9, 10] / 현재 풀이 값 = ", merge_sort([-1, -1, 0, 1, 6, 9, 10]))