본문 바로가기

분류 전체보기138

병합 정렬(Merge sort) 병합정렬 시간복잡도 공간복잡도 모든 값을 비교해야하므로 N 반복을 거듭할 때마다 반씩 줄어듦으로 log N O(N log N) 배열을 병합할 때 병합 결과를 담아놓을 배열이 필요함 O(N) 주어진 요소가 각 1개가 될 때까지 분할한 후 각 요소들을 병합하는 과정에서 비교하여 정렬하는 방식. 분할 정복과 재귀 용법을 이용하는 알고리즘. [7, 4, 5, 1, 3] 예를 들어 이렇게 주어진 배열을 정렬한다고 해보자. 먼저 모든 요소가 1개가 될 때까지 반으로 쪼갠다. 전체 배열의 길이를 2로 나눈 후 소숫점과 나머지는 버리고 몫만 얻어서 배열을 반으로 나눈다. len(input_array) // 2 => [7, 4] [5, 1, 3] => [7] [4] [5] [1, 3] => [7] [4] [5] [1] .. 2022. 7. 13.
삽입 정렬(Insertion sort) 삽입정렬 시간복잡도 공간복잡도 전체 요소를 순회하기 위해 N 검색 범위를 넓혀가며 전체 요소까지 비교하기 위해 N N x N = O(N²) 비교 후 배열 내 스왑을 하기 위해 O(1) 정렬 범위를 한칸씩 확장하여 새로 비교할 값을 이미 정렬된 값과 비교하여 정렬하는 알고리즘 [7, 4/, 5, 1, 3] 예를 들어 이렇게 주어진 배열을 정렬한다고 해보자. 배열은 총 5개의 요소를 가지고 있다. 이 중 맨 앞의 2개 요소만 두고 첫번째 비교를 시작한다. 7과 4중 4가 더 작기 때문에 둘의 위치를 바꿔준다. [4, 7/, 5, 1, 3] 첫번째 순회가 끝났다. 두번째 순회를 시작한다. 이제 검색범위를 넓혀 3번째 요소, 2번 인덱스에 있는 요소를 추가하여 뒤에서부터 비교한다. 7과 5중 5가 더 작기 때문.. 2022. 7. 12.
선택정렬(Selection sort) 선택정렬 시간복잡도 공간복잡도 전체 요소를 순회하기 위해 N 요소들을 비교하며 가장 작은 요소를 찾기 위해 N N x N = O(N²) 비교 후 배열 내 스왑을 하기 위해 O(1) 배열을 순회하며 가장 작은 요소를 찾아 맨 앞에 위치시키는 방식의 정렬 [7, 4, 5, 1, 3] 예를 들어 이렇게 주어진 배열을 정렬한다고 해보자. 배열은 총 5개의 요소를 가지고 있다. 맨 앞의 요소부터 전체 요소와 비교해가며 가장 작은 요소를 찾아 비교요소와 위치를 바꾼다. 먼저 가장 작은 요소의 index를 0번으로 초기화한다. 첫번째 loop는 0번을 기준으로 비교한다. 0번과 1번, 0번과 2번, 0번과 3번, 0번과 4번하며, 만약 비교하는 요소가 가장 작은 요소(현재 0번)보다 더 작다면 가장 작은 요소의 인덱.. 2022. 7. 12.
버블정렬(Bubble sort) 버블정렬 시간복잡도 공간복잡도 전체 요소를 순회하기 위해 N 인접 요소를 비교하기 위해 N N x N = O(N²) 인접 요소 비교 후 스왑을 하기 위해 O(1) 버블 정렬은 인접한 두 요소를 비교하며 큰 값을 뒤로 보내는 방식이다. [4, 1, 3, 5, 6, 2] 예를 들어 이렇게 주어진 배열을 정렬한다고 해보자. 배열은 총 6개의 요소를 가지고 있다. 이때 배열의 0번 요소부터 인접한 두 개 요소를 비교한다. 첫번째 loop는 0번과 1번, 1번과 2번, 2번과 3번, 3번과 4번, 4번과 5번을 비교한다. 만약 앞의 요소(i번째)가 뒤의 요소(i + 1번째)보다 크다면 둘의 위치를 바꾸고, 뒤의 요소가 더 크다면 다음 비교로 넘어간다. 두번째 loop는 다시 0번과 1번, 1번과 2번, 2번과 3.. 2022. 7. 12.

티스토리툴바