NAIAHD

탐색은 : 여러 개의 자료 중에서 원하는 것을 찾아내는 것

정렬은 : 주어진 자료를 순서에 맞춰 나열하는 것

 

07. 순차 탐색 

 

주어진 리스트에 특정한 값이 있는지 찾아 그 위치를 돌려주는 알고리즘

sequential search

 

1. 순차 탐색으로 특정 값의 위치 찾기

def search_list(a, x):

  n = len(a)

  for i in range(0,n):

     if x == a[i]:

        return i

  return -1

 

2. 알고리즘 분석

계산 복잡도 O(n)

 

08. 선택 정렬

1. 선택 정렬로 줄 세우기

2. 쉽게 설명한 선택 알고리즘

def find_min_idx(a):

   n = len(a)

   min_idx = 0

   for i in range(1, n):

      if a[i] < a[min_idx]:

         min_idx = i

   return min_idx

 

def sel_sort(a):

  result = []

  while a:

     min_idx = find_min_idx(a)

     value = a.pop(min_idx)

     result.append(value)

  return result

 

3. 일반적인 선택 알고리즘

def sel_sort(a):

  n = len(a)

  for i in range(0,n-1):

    min_idx = i

    for  j in range(0,n-1):

      if a[j] < a[min_idx]:

         min_idx = j

  a[i], a[min_idx] = a[min_idx], a[i]

 

4. 알고리즘 분석

O(n^2)

 

09. 삽입 정렬 

리스트 안의 자료를 작은 수 부터 큰 순서로 배열하는 정렬 알고리즘

1. 삽입 정렬로 줄 세우기

2. 쉽게 설명한 삽입 정렬 알고리즘

def find_ins_idx(r, v):

  for i in range(0, len(r)):

     if v < r[i] :

       return i

  return len(r)

def ins_sort(a):

  result = []

  while a:

    value = a.pop(a)

    ins_idx = find_ins_idx(result , value)

    result.insert(ins_idx , value)

  return result

3. 일반 적인 삽입 정렬

def ins_sort(a):

  n = len(a)

  for i in range(1, n):

    key = a[i]

    j = i-1

    while j >= 0 and a[j] < key:

       a[j+1] = a[j]

       j -= 1

    a[j+1] = key

4. 알고리즘 분석 

O(n^2)

 

문제 10 : 병합 정렬

리스트 안의 자료를 작은 수부터 큰 수 순서로 배열하는 정렬 알고리즘을 만들어 보세요.

1. 병합 정렬로 줄 세우기

2. 쉽게 설명한 병합 정렬 알고리즘

def merge_sort(a):

  n = len(a)

  if n <= 1:

    return a

  mid = n //2

  g1 = merge_sort(a[:mid])

  g2 = merge_sort(a[mid:])

  result = []

  while g1 and g2:

    if g1[0] < g2[0]:

      result.append(g1.pop(0))

    else:

      result.append(g2.pop(0))   

    while g1:

      result.append(g1.pop(0))

    while g2:

      result.append(g2.pop(0))

  return result

3. 병합 정렬에서의 재귀 호출

4. 일반적인 병합 정렬 알고리즘 

def merge_sort(a):

  n = len(a)

  if n <= 1:

    return

  mid = n //2

  g1 = a[:mid] 

  g2 = a[mid:]

  merge_sort(g1)

  merge_sort(g2 )

  i1 = 0

  i2 = 0

  ia = 0

  while i1< len(g1) and i2< len(g2):

    if g1[i1] < g2[i2]:

      a[ia] = g1[i1]

      i1 += 1

      ia += 1

    else:

      a[ia] = g2[i2]

      i2 += 1

      ia += 1

  while i1< len(g1):

      a[ia] = g1[i1]

      i1 += 1

      ia += 1

  while i2< len(g2):

      a[ia] = g1[i2]

      i2 += 1

      ia += 1

  5. 알고리즘 분석

 

문제 11. 퀵정렬

그룹을 둘로 나눠 재귀 호출하는 방식

def quick_sort(a):

  n = len(a)

  if n <=1:

    return a

  pivot = a[-1]

  g1 = []

  g2 = []

  for i in range(0,n-1):

    if a[i] < pivot:

      g1.append(a[i])

    else:

      g2.append(a[i])

  return quick_sort(g1)+[pivot] + quick_sort(g2)

 

def quick_sort_sub(a, start, end):

  if end - start <= 0:

     return 

  pivot = a[end]

  i = start

  for j in range(start, end):

    if a[j] <= pivot:

      a[i], a[j] = a[j] , a[i]

      i+=1

  a[i],a[end] = a[end],a[i]

  quick_sort_sub(a, start, i-1)

  quick_sort_sub(a, i+1, end)

 

def quick_sort(a):

  quick_sort_sub(a, 0, len(a)-1)

 

문제 12. 이분 탐색

둘로 나눈다 탐색할 자료를 둘로 나누어 찾는 값이 있을 법한 곳만 탐색하기 때문에 자료를 하나하나 찾아야 하는 순간 탐색보다 원하는 자료를 훨씬 빨리 찾을 수 있습니다.

 

def binary_search(a, x):

  start = 0

  end = len(a) -1

  while start <= end:

    mid = (start+end)//2

    if x == a[mid]:

      return mid

    elif x > a[mid]:

      start = mid +1

    else:

      end = mid-1

  return -1

 

 

 

 

 

 

출처 : 모두의 알고리즘 with 파이썬