Data Structures and Algorithms (5)

Data Structure and Algorithms (5)

정렬

정렬(sorting) : 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것

1. 버블 정렬 (bubble sort)

인접한 두 데이터를 비교해서 앞에 있는 데이터가 뒤에 있는 데이터보다 크면 자리를 바꾸는 정렬 알고리즘

try

4321 - 3421 - 3241 - 3214
     - 2314 - 2134 
     - 1234
ㅤ
54321 - 45321 - 43521 - 43215
      - 34215 - 32415 - 32145
      - 23145 - 21345
      - 12345
ㅤ
✔ n개의 숫자가 있다면 n-1번의 로직 적용
✔ 로직이 한 번 적용될 때 마다 뒤에서부터 숫자가 1개씩 결정

pseudo code

1. for num in range(len(data)-1)
2. swap = 0 (교환이 되었는지 확인하는 변수)
3. 반복문 안에서 len(data)-num-1만큼 확인
4. 값을 비교하고 값 변경 필요하면 변경
5. swap = 1
6. 첫 번째 반복문에서 swap = 0이면 break

code

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

시간복잡도 : O(n^2)
ㅤ
ㅤ
ㅤ

ㅤ
ㅤ

2. 삽입 정렬 (insertion sort)

두 번째 인덱스(key)부터 시작하여 해당 인덱스 앞에 있는 데이터부터 비교해서 key 값이 작으면 앞에 있는 데이터를 뒤 인덱스로 복사
-> key값이 더 큰 데이터를 만날때까지 반복, 큰 데이터를 만난 위치 바로 뒤에 key값 이동

try

54321 (4)
45321 (3)
34521 (2)
23451 (1)
12345
ㅤ
✔ 총 n-1번의 로직
✔ 인덱스 위치 
  1) 1+1 -> 1+1-1
  2) 2+1 -> 2+1-1 -> 2+1-1-1
  3) 3+1 -> 3+1-1 -> 3+1-1-1 -> 3+1-1-1-1
  4) 4+1 -> 4+1-1 -> 4+1-1-1 -> 4+1-1-1-1 -> 4+1-1-1-1-1
✔ 해당 인덱스에서 크기 비교 후 swap / break 결정

pseudo code

1. for num in range(len(data)-1)
2. index2 : range(num+1, 0, -1)
3. 크기 비교 후 swap / break

code

def insertionsort(data):
  for index in range(len(data)-1):
    for index2 in range(len(data)+1, 0, -1):
      if data[index2] < data[index2-1]:
        data[index2], data[index2-1] = data[index2-1], data[index2]
      else:
        break
  return data

시간복잡도 : O(n^2)
ㅤ
ㅤ
ㅤ

ㅤ
ㅤ

3. 선택 정렬 (selection sort)

탐색을 통해 최솟값을 찾아 배열의 맨 앞에 위치한 값 중 적용이 안 된 값과 교체

try

543
ㅤ
✔ 총 n-1번의 로직
✔ 인덱스 위치 
  1) 1+1 -> 1+1-1
  2) 2+1 -> 2+1-1 -> 2+1-1-1
  3) 3+1 -> 3+1-1 -> 3+1-1-1 -> 3+1-1-1-1
  4) 4+1 -> 4+1-1 -> 4+1-1-1 -> 4+1-1-1-1 -> 4+1-1-1-1-1
✔ 해당 인덱스에서 크기 비교 후 swap / break 결정

pseudo code

1. for num in range(len(data)-1)
2. 최솟값 탐색
3. 탐색 후 교체

code

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

시간복잡도 : O(n^2)

본 게시글은 fastcampus 이준희강사 수업을 듣고 개인적으로 정리한 내용임을 밝힘.