jhjo.tech jhjo.tech

Quick Sort Divide and Conquer(분할 정복)을 통해서 정렬을 하는 방식입니다. 최선 또는 평균적인 케이스에서 불필요한 데이터의 이동을 줄이고 한 번 결정된 피벗들이 추후 연산에서 제외되기 때문에 다른 정렬 알고리즘에 비해서 빠르고, 정렬하고자 하는 배열 안에서 교환을 진행하기 때문에 추가적인 메모리 공간이 필요하지 않다는 장점이 있습니다. Merge Sort와 달리 불균형 분활을 하기 때문에 정렬된 배열에서 오히려 수행 시간이 더 걸리다는 단점도 있습니다. Divide and Conquer (분할 정복) 문제를 작은 2개로 분리하고 각각 해결하고 결과를 모아서 문제를 해결하는 방식입니다. Code void swap(int arr[], int index1, int index2) { i..

Insertion Sort 2번째 아이템부터 시작하며, 앞에서부터 차례대로 정렬된 부분과 비교하여 자신의 위치를 찾아 삽입하여 정렬하는 알고리즘입니다. Process 1부터 6까지 랜덤으로 들어 있는 배열이 있습니다. Ascending(오름차순)으로 정렬합니다. 비교하고자 하는 값(2번째 아이템)을 가지고 비교를 시작합니다. 첫 번째 아이템이 작으면 삽입을 진행하지 않습니다. (현재 사이클 종료) 1 사이클이 종료되었습니다. 2사이클 시작 세 번째 아이템을 비교 값으로 가지고 있습니다. 두 번째 아이템과 비교하여 두 번째 아이템이 크면 교환 크지 않으면 사이클 종료 여기서는 두 번째 아이템이 더 크기 때문에 교환 후 다음 비교를 진행합니다. 첫 번째 아이템과 비교 했을때는 비교 값이 더 크기 때문에 현재..

Selection Sort 정렬할 위치를 먼저 선택한 뒤 그 자리에 오는 값을 찾고(Compare) 값이 있다면 교환(Swap)하는 방식의 알고리즘입니다. Process 1부터 6까지 랜덤으로 들어 있는 배열이 있습니다. Ascending(오름차순)으로 정렬합니다. 오름차순 이기 때문에 0번 인덱스부터 최소값으로 정렬 되어야 합니다. 0번 인덱스에 넣을 최소 값의 인덱스를 찾습니다. 0번 인덱스의 아이템이 최소 값이 아니라면 최소값이 위치한 인덱스의 값과 교환합니다. - 가장 작다면 교환 하지 않습니다. 여기까지 1 사이클입니다. 이제 0번 인덱스는 정렬이 완료되었기 때문에 1번 인덱스부터 최소 값을 찾습니다. 최소 값이 다른 인덱스라면 값을 Swap 합니다. 정렬이 완료될 때까지 위의 사이클을 반복합니..

Bubble Sort 정렬 과정에서 원소의 이동이 거품이 수면으로 올라가는 모습을 보이기 때문에 지어진 이름입니다. 서로 인접한 두 원소를 비교하여 주어진 조건에 맞으면(또는 맞지 않으면) 자리를 교환하여 정렬하는 알고리즘입니다. 중요한 것은 Compare(비교) 후 Swap(교환)입니다. Process 1부터 6까지 랜덤으로 들어 있는 배열이 있습니다. Ascending(오름차순)으로 Bubble Sort 하려고 합니다. 첫 번째 아이템(4)과 두 번째 아이템(6)을 비교합니다. 두 번째 아이템이 더 크기 때문에 아이템을 교환하지 않습니다. 두 번째(6) 세 번째(5) 인덱스의 아이템을 비교합니다. 세 번째 아이템이 더 작기 때문에 아이템을 교환합니다. 위 과정을 마지막 인덱스까지 반복합니다. 여기까지..

Big-O 표기법 알고리즘을 시간(초단위)으로 표현을 하기에는 하드웨어에 따라서 더 빠를 수도 느릴 수도 있기 때문에 비교를 할 수가 없습니다. 그렇기 때문에 알고리즘의 성능을 수학적으로 표현하기 위한 표기법이 필요했고, 완료까지 걸리는 절차(STEPS)의 수를 속도로 보고 이를 Big-O 표기법을 사용해서 표기합니다. 예를 들어 Linear Search는 한 번에 하나씩 찾기 때문에 10개의 아이템이 있으면 10번의 스탭을 사용하고, 20개가 있으면 20번의 스탭을 거쳐야 찾을 수 있습니다. 이것은 입력되는 데이터의 사이즈 인 Input size가 N개이면 N번의 Step이 요구된다는 뜻이며, 그렇기 때문에 Linear Serarch의 시간 복잡도는 O(N)이 된다고 볼 수 있습니다. 이렇게 Big-O..