알고리즘 기초

학습내용

SWAP

파이썬에서의 swap

1. # 첫번째 방법
   a = 3
   b = 1
   
   temp = a
   a = b
   b = temp
   
   print(a,b)

2. # 두번째 방법
   a = 3
   b = 1
   
   a, b = b, a # 파이썬에서는 한 줄로 변경가능
   
   print(a,b)

Search algorithm basic

• 선형 검색

  • 한 번에 하나씩 모두 검색하는 방법
  • 시간 복잡도 : O(n)

  def linear_search(linear_arr, search_number):
      for i in range(len(linear_arr)):
        if linear_arr[i] == search_number:
          return i
  
  linear_arr = [5,22,87,1,3]
  search_number = 1
  print("search index : ",linear_search(linear_arr, search_number))

• 이진 검색

  • 반복을 통해 숫자를 반으로 줄이면서 검색
  • 이미 정렬된 경우에만 작동
  • 시간 복잡도 : O(log n)

  def binary_search(test_list, search_item):
  
       low = 0
       high = len(test_list) - 1
  
       while low <= high:
           middle = (low + high) // 2   # middle을 지정해서 검색속도를 빠르게 한다.
           guess = test_list[middle]
  
           if guess == search_item:
               return middle
           if guess > search_item:
               high = middle - 1
           else:
               low = middle + 1
       return None

Iterative Sorting

• selection sort(선택정렬)

  • 가장 작은 노드를 선택
  • 가장 왼쪽에 있는 노드와 비교하며 교환
  • 앞의 두 과정을 반복
  
  • 시간 복잡도 : O(n^2)
  • 안정적이지않음 : 중복이 있을 경우, 원래 순서 유지가 안됨
  • 실제 예시 : 도서관 책 정리

  # 선택정렬 소스코드
  
  def selection_sort(items):
      
      for i in range(0, len(items) - 1):    # 외부 반복문(루프)
  
          cur_index = i
          smallest_index = cur_index
          
          for j in range(cur_index + 1, len(items)):  # 내부루프
                 # 최소값찾는 로직
                 if items[smallest_index] > items[j]:
                     smallest_index = j
  
          # swap
          items[smallest_index], items[cur_index] = items[cur_index], items[smallest_index]
   
      return items

• Insertion sort(삽입정렬)

  • 특정 노드를 이미 정렬된 배열과 비교
  • 특정 노드보다 작은 값을 갖고 있는 노드가 나올때까지 비교를 진행
  • 작은 값의 노드가 발견되면 그 오른쪽 인덱스에 특정 노드를 삽입
  • 아직 정렬이 되지않은 노드 중 하나를 골라 앞의 과정을 반복

  

  출처 : https://runestone.academy/runestone/books/published/pythonds/SortSearch/TheInsertionSort.html

  • 소량의 데이터를 정렬하기 위한 효율적인 알고리즘
  • 시간 복잡도 : O(n^2)

  # 삽입정렬 소스코드
  
  def ins_sort(unsort_list):
  
      loop_number = len(unsort_list)          # 반복횟수를 위한 길이설정
  
      # 앞쪽에 있는 노드들을 검색하기 위한 반복문
      for compare_index in range(loop_number):    # 비교하려는 위치부터 loop_number만큼 반복
          compare_value = unsort_list[compare_index]  
          prev_position = compare_index - 1   # 이전 노드값에 대한 인덱스를 가리킴
          
          # 비교연산 후 삽입을 진행하는 반복문
          while prev_position >= 0 and unsort_list[prev_position] > compare_value:    
                # 1-1차작업 : swap을 위한 작업
              unsort_list[prev_position], unsort_list[compare_index] = unsort_list[compare_index], unsort_list[prev_position]
              prev_position = prev_position - 1
               # 1-2차작업 : 비교된 더 큰 값을 (이전노드+1) 인덱스에 삽입
              compare_index = compare_index - 1
              
      return unsort_list
              
  test_arr = [5,3,1,6]
  ins_sort(test_arr)

• Bubble sort(버블정렬)

  • 서로 이웃한 두 원소의 크기를 비교한 결과에 따라 교환을 반복하는 알고리즘
  • 첫 번째 항목부터 마지막 항목까지 두개씩 짝지어 비교하고, 대소에 따라 교환
  
  • 시간 복잡도 : O(n^2)
  • 이웃노드만 교환하므로 안정적임

   버블정렬 소스코드
  def bubble_sort(li):
      length = len(li) - 1
  
      for i in range(length):
          for j in range(length-i):
              if li[j] > li[j+1]:
                  li[j], li[j+1] = li[j+1], li[j]
  
           # 외부 반복문(아래 그림에서 전체 리스트에 대해 정렬이 완료되었는지 검사하고 패스해줌)
            # 내부 반복문(아래 그림에서 하나의 리스트의 개별 값을 비교하고 교체시킨다)
              # 현재 인덱스의 값과 다음 인덱스의 값 비교
                  # 비교한 것에 따라 정렬을 위한 인덱스 교환 작업
  
  li = [10, 2, 1, 7, 4, 3, 0]
  bubble_sort(li)
  print(li)