![]()
이전의 포스팅에서 버블 정렬과 선택 정렬을 알아보았는데, 둘 다 효율성은 O(N2)이지만 선택 정렬이 실제로는 두배 더 빠르다는 것을 알 수 있었다. 이번에는 삽입 정렬(insertion sort)을 배우면서 최악의 경우가 아닌 다른 시나리오를 분석하는 것에 중점을 두고 어떠한 장점이 있는지 알아 보겠다. 삽입 정렬의 수행 순서 삽입 정렬을 수행 할 배열은 [2, 4, 7, 1, 3] 이다. 먼저 loop1이다. 먼저 인덱스 1의 값을 확인한다. 임시로 인덱스1(값2)를 삭제한 후 temp_value 변수에 저장한다 인덱스 - 1(값4)와 비교한다. 4가 2보다 크므로 4를 오른쪽으로 쉬프트 한다. 더이상 비교할 인덱스가 없으므로 temp_value를 -1인덱스에 삽입한다. 첫번쨰 루프의 결과는 [2, ..
이전에는 효율성이 O(N2)인 데이터 정렬 알고리즘인 버블 정렬(bubble sort)을 살펴보았다. 이번에는 선택 정렬(selection sort)라는 다른 정렬 알고리즘을 알아보고 버블 정렬과 효율성을 비교해 보겠다. 선택 정렬의 루프를 알아보자. 먼저 인덱스 0에 들어 있는 값을 확인하며 시작하여 최솟값으로 지정한 후, 다음 인덱스와 비교한 다음 최솟값을 결정한다. loop1 min_Index = 0 (값 = 5) [5, 3, 2, 1, 4] 인덱스 0과 1의 비교 min_Index = 1 (값 = 3) [5, 3, 2, 1, 4] 인덱스 1과 2의 비교 min_Index = 3 (값 = 2) [5, 3, 2, 6, 4] 인덱스 2과 3의 비교 min_Index = 3 (값 = 2) [5, 3, 2..
버블 정렬은 단순 정렬(simple sort)중 하나로 알려져있으며 매우 기본적인 정렬 알고리즘이지만 더욱 빠르다고 알려진 정렬 알고리즘보다 비효율적이다. 버블 정렬 예제를 살펴보자. 먼저 [ 6, 3, 1, 2, 4, 5 ] 이라는 배열을 정렬하고 싶다고 가정하자. 1loop [ 6, 3, 1, 2, 4, 5 ] 먼저 6과 3을 비교하여 순서가 맞지 않음을 확인하고 6과 3을 교환한다. [3, 6, 1, 2, 4, 5 ] 그다음으로 6과 1을 비교하여 순서가 맞지 않음을 확인하고 6과 1을 교환한다. [3, 1, 6, 2, 4, 5 ] [3, 1, 2, 6, 4, 5 ] [3, 1, 2, 4, 6, 5 ] 1loop result = [3, 1, 2, 4, 5, 6 ] 이렇게하여 1loop가 끝난다. 2..
이진 탐색은 정렬된 데이터에서 특정한 값을 찾고자할 때 O(logN)의 성능으로 빠르게 값을 찾을 수 있는 장점이 있다. 2023.04.20 - [Data Structures & Algorithms] - 빅오 big-O 빅오 big-O 빅오 표기법 서로 간의 시간복잡도를 쉽게 소통할 목적으로 자료구조와 알고리즘의 효율성을 간결하게 일관된 언어로 설명하기 위한 수학적 언어이다. 빅오 표기법을 이용해 주어진 알고리즘 chaehun97.tistory.com O(logN)의 설명은 이전의 글에서 간략하게 써둔 것이 있으니 참고해보자.. 부족한 설명으로 이해가 되지 않을 수 있으니.. 다른 포스팅을 보는 것이 효율적일 수도 있다. 나중에 수정할 예정이니 참고만 해보자. 아마도 코드로 구현해보면 어떤 식으로 효율적..
