알고리즘강의 04. 복습

이 글은 블로그주인장이 여태 공부했던 알고리즘 독학 및 강의들의 내용을 정리하는 포스팅입니다.

정렬(1)

정렬이란 데이터를 순서대로 나열하는 방법을 의미

[3,0,4,2,1]
[0,1,2,3,4] #오름차순
[4,3,2,1,0] #내림차순

버블정렬(Bubble Sort)

• 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지
  막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬하는 방식

• 시간복잡도 O(N^2)

# 파이썬 코드
def bubble_sort(array):
    n=len(array) 
    for i in range(n-1): # 리스트-1의 크기만큼
        for j in range(n-i-1): #array[j] 와 array[j + 1] 을 비교할거라, 
        # 마지막 원소까지 가지 않아도 됨
            if array[j] > array[j+1]:
                array[j], array[j + 1] = array[j + 1], array[j]
    return array

// C 코드
for (int i = 1; i <n; i++) {
		for (int j = 0; j < n-i; j++) {
			if (arr[j] > arr[j + 1]) swap(&arr[j], &arr[j + 1]);
		}
	}

선택정렬(Selection Sort)

• 다음과 같이 데이터들이 일렬로 쭉 있는데,
  한번 쓱 둘러보면서 가장 작은 데이터를 찾음
  그리고 전부 다 봤다면, 그 중 가장 작은 데이터를 맨 앞으로 이동한 다음에 또 둘러보면서 두 번째로 작은 데이터를 두 번째에 배치 시킴
• 시간복잡도 O(N^2)

#python 소스코드
def selection_sort(array):
    n=len(array)
    for i in range(n-1): # Q. 여기서 왜 5 - 1 일까요?
        min_index=i
        for j in range(n-i): # A. 맨 마지막 비교는 하지 않아도 되기 때문
            if array[i + j] < array[min_index]:
                min_index = i + j #변경
        array[i], array[min_index] = array[min_index], array[i]
    return array #오름차순 정렬

//c 소스코드
for (int i = 0; i < n-1; i++) {
		min = i
		for (int j = i+1; j < n; j++) {
			if (min > arr[j]) {
				min = arr[j];
				index = j;
			}
		}
		swap(&arr[i], &arr[index]);
	}

삽입정렬(Insert Sort)

• 각 숫자를 적절한 위치에 삽입하는 정렬 기법, 들어갈 위치를 선택하는 데에 N 번 ,선택하는 횟수로 N 번이므로
• 시간복잡도: 시간복잡도 O(N^2)

#python 소스코드
def insertion_sort(array):
    n = len(array)
    for i in range(1, n):
        for j in range(i):
            if array[i - j - 1] > array[i - j]:
                array[i - j - 1], array[i - j] = array[i - j], array[i - j - 1]
            else:
                break #비교를 안해도 되는 순간이 오면 break
    return array

//c 소스코드
for (int i = 0; i < n - 1; i++) {
		int j = i;
		while (j>=0 && a[j]>a[j+1]){
			swap(&a[j], &a[j + 1]);
			j--;
		}
	}

참고

• 학부생 시절 자료구조 강의
• 알고보면 알기 쉬운 알기쉬운 알고리즘 -스파르타 코딩클럽
• 컴퓨터공학 전공 올인원 패키치 - 패스트 캠퍼스
• 소스코드
  https://github.com/BOLTB0X/Sparta-Algorithm/tree/main/week_3
  https://github.com/BOLTB0X/DataStructure_Argolithm/tree/main/05_Sort