이쯤에서 슬슬 앞의 정렬을 까먹은분을 위해 짧막 상식 우리가 배웠던 정렬의 방식을 짧게 설명하고자 한다 1. 계수 정렬 = 들어온 숫자를 배열로 받아서 들어온 숫자를 카운트하여 정렬 2. 선택 정렬 = 인덱스의 순서대로 숫자를 지정하며 해당 숫자를 직접 찾아 둘이서 교환 3. 삽입 정렬 = 뒷자리 숫자와 앞자리 숫자를 비교하고 더 작은 숫자를 비교하고 해당 숫자의 앞자리가 본인보다 작은것을 찾을때 까지 비교한다. 과정(우리는 오름차순을 기준으로 한다.) 1. 앞에서부터 현재 원소와 바로 다음의 원소를 비교한다. 2. 현재 원소가 다음 원소보다 크면 원소를 교환한다. 3. 다음 원소로 이동하여 해당 원소와 그 다음 원소를 비교한다. 거품 정렬은 정렬규칙이 있다 총 라운드는 (배열 크기 - 1)번 진행하고 ..
선택 정렬은 말 그대로 현재 위치에 들어갈 데이터를 찾아 선택하는 알고리즘이다. 데이터를 비교하며 들어가기 때문에 "비교정렬" 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않기 때문에 "제자리 정렬" 마지막으로 "불안정 정렬"이다. 과정을 알아보자 주어진 리스트에서 최솟값을 찾는다. 최솟값을 맨 앞 자리의 값과 교환한다. 맨 앞 자리를 제외한 나머지 값들 중 최솟값을 찾아 위와 같은 방법으로 반복한다. 저런식으로 배열을 하는것이 선택 정렬이다 중요한것이 있다 그림으로는 표현하지 않았지만 index8까지는 계속해서 정렬하고 마지막 인덱스를 제외하고 정렬을 마친다 그 이유는 N-1개가 정렬이 되어있다는 뜻으로 결국 마지막 원소는 자연적으로 최댓값이 되었다는 뜻이다. 구현은 나의 깃허브에 해놓..
우선순위 큐와 힙은 정말 많이 닮았다. 오죽하면 우선순위 큐 = 힙이라고 아는 분들도 적지 않을 것이다. 결론만 말하자면 둘의 차이는 우선순위 큐는 ADT(Abstract Data Type)이고 힙은 Data Structure이다. ※큐(Queue) = 먼저 들어오는 데이터가 먼저 나가는 구조(FIFO - First In First Out) ADT(Abstract Data Type) "추상적 자료형"이라는 뜻이다. 있는 그대로를 해석해 보자면 핵심 개념이나 기능을 간추려 내어 데이터를 식별하는 구분, 연산, 저장 방법 등을 모두 포함한 것 추상화를 통해 얻어낸 자료형 이게 무슨 말이냐면 자료 구조와는 달리 구현내용은 명시하지 않는다. 오로지 인터페이스만 제공할 뿐 특징이 있다. ● 추상화를 통해 정의된다..
시간복잡도가 굉장히 빠른 counting sort에 대해 알아보자 카운팅 정렬의 메커니즘을 알아보자 짧게 얘기하자면 데이터의 값이 몇 번 나왔는지 세주는 것(counting)이다. 말보단 그림으로 확인해 보자 1 Step) 우린 이런 배열을 받았다 index 0 1 2 3 4 5 6 7 8 vlaue 4 7 0 2 7 5 1 4 3 그럼 count정렬은 각 인덱스에 들어가 있는 숫자의 개수를 정해서 받은 숫자를 인덱스로, 들어온 횟수를 value로 지정한다. index 0 1 2 3 4 5 6 7 value 1 1 1 1 2 1 0 2 이런 식으로 각 인덱스로 들어온 숫자를 counting 해서 넣는 것이다. 2.Step) counting 한 배열을 누적합으로 바꿔준다. 0번째 인덱스와 1번째 인덱스 누..
자 이쯤에서 슬슬 앞의 정렬을 까먹은분을 위해 짧막 상식 우리가 배웠던 정렬의 방식을 짧게 설명하고자 한다 1. Counting Sort (계수 정렬) - O(n) = 배열을 생성해서 그 안에 숫자를 받는다 그리고 같은 숫자가 있다면 카운트하여 인덱스로 저장해두었다가 정렬할때 한개씩 나열하며 정렬한다. 2. Selection Sort (선택 정렬) - O(n2) = 무작위로 받은 숫자를 쭈욱 나열하고 인덱스에 위치해야하는 수를 직접 찾아 해당 인덱스로 보내고 거기있던 수와 바꿔치기 한다. 3. Insertion Sort (삽입 정렬) - O(n2) = 무작위로 받은 숫자를 나열하고 첫번째 인덱스와 두번째 인덱스를 비교한다. 그리고 이 정렬은 인덱스가 커지더라도 계속해서 앞의 숫자와 비교하며 수를 정렬한다..
자 제목 부터 삽입 정렬이 나온다. 그럼 기본적으로 삽입 정렬에 대한 지식이 필요하지 않을까? 한번 보고 왔으면 좋겠당 삽입정렬 삽입 정렬(Insertion Sort) 이번에는 삽입 정렬을 배워보겠다. 간단히 정의하자면 현재 비교하고자 하는 target과 그 이전의 원소들과 비교하며 자리를 교환하는 정렬이다. 삽입정렬 역시 "안정 정렬"이다. 삽입 정렬의 과정 latewalk.tistory.com 앞서 봤던 삽입정렬은 선형탐색을 통한 원소가 들어갈 위치를 잡았다. 하지만 이진 삽입 정렬은 다르다. 이진 탐색(Binary Search)을 이용해 보자 천천히 생각해보자 저 위에 삽입 정렬은 target으로 숫자를 설정하고 그 숫자를 맞는 위치를 찾기위해 반복을 계속했다 이게 무슨 문제인가? 당연한거 아닌가?..
이번에는 삽입 정렬을 배워보겠다. 간단히 정의하자면 현재 비교하고자 하는 target과 그 이전의 원소들과 비교하며 자리를 교환하는 정렬이다. 삽입정렬 역시 "안정 정렬"이다. 삽입 정렬의 과정 현재 타깃이 되는 숫자와 이전 위치에 있는 원소들을 비교한다. (첫 번째 원소는 두 번째부터 비교한다.) 타깃이 되는 숫자가 이전 위치에 있던 원소보다 작다면 위치를 서로 교환한다. 그다음 타깃을 찾아 위와 같은 방법으로 반복한다. 짧게 얘기하면 배열을 쭈욱 나열하고 앞뒤로 서로 비교하며 오름차순으로 정렬하는 것이다. 첫번째 원소는 타겟이 되어도 비교할 전 원소가 없어서 2번째 원소부터 타겟으로 잡고 시작한다. 구현은 나의 깃허브에 해놓았다 시간이 된다면 보는것을 적극 추천한다 https://github.com/..
