ITeus

Radix Sort는 비교기반이 아닌 값의 분포를 이용한 정렬 알고리즘 입니다. Radix이 한글로 기수라고 하는데, 나누기를 할때 몫에 해당하는 값이라고 합니다. 이때 10^n의 기수를 생각하면, 각 자리수를 이용해서 값을 정렬하는 알고리즘이라고 볼 수 있습니다. 첫번째 Element부터 1의자리를 비교하여, 해당 1의자리에 해당하는 List로 삽입을 진행합니다. 이렇게 모든 Element에 대해서 진행 후, 삽입된 List를 순서대로 풀어주면 한번의 Cycle이 끝납니다. 보시면 첫째자리의 값 기준으로는 모든 Element가 정렬된 것을 볼 수 있습니다! 이제 두번째 보시면, 왜 이런작업을 하는지 알 수 있습니다. 보시면, 10의자리 숫자를 기준으로 정렬할 때 1의자리 숫자의 정렬이 유지됩니다.(10..

Bubble Sort는 가장 기본적인 정렬 알고리즘 입니다. 맨 왼쪽의 Element를 순차적으로 인접 Element와 비교하여, 값이 큰 Element를 오른쪽으로 옮기는 방식입니다. 매우 간단한 것을 알수 있습니다. 1번의 Cycle이 끝나면, 마지막 Element를 제외한 나머지 부분배열에서 동일한 정렬을 진행하면, 모든 Element가 정렬되게 됩니다. 해당 알고리즘은 n, n-1, n-2, n-3..... 2, 1번의 비교를 진행하게 되어, 총 n(n-1)/2번의 비교가 이뤄지는 알고리즘 입니다. 그래서 알고리즘의 시간복잡도는 O(n^2)의 시간복잡도를 보여주는 알고리즘이 되겠습니다 :) (고정된 시간이 걸리며, 가장 성능이 안좋습니다 ㅠ) 원래는 정렬 알고리즘 에서 가장 처음 나오는 알고리즘인..

Heap이란 완전 Binary트리를 형성하는 자료구조의 일종입니다. teus-kiwiee.tistory.com/29 Heap 이때 Max_heap과 Min_heap이 있으며, 아래 예시를 보면 이해하기 쉽습니다. Random한 Array를 Max Heap 또는 Min Heap을 만들었을 경우의 모습입니다. 따로 설명이 필요없어보이네요 이때 Tree구조를 언어에서 teus-kiwiee.tistory.com 이때, Heap의 형성 후 Top Node의 값이 Max Or Min 값을 갖게 됩니다. 이때 Top Node의 값을 활용해서 Data를 정렬하는 방법을 Heap Sort 알고리즘 이라고합니다. 알고리즘은 1. Random Array에 Max heap 형성 2. 0번 Node의 값 추출 3. 마지막 No..

1. Insert Sort Insert Sort알고리즘은 주어진 배열을 정렬하는 알고리즘 중 하나입니다. 해당 알고리즘은 정렬된 Array를 구축하고, 새로운 원소를 정렬된 Array에 Insert하는 알고리즘이어서 Insert 정렬이라고 불립니다. 알고리즘은 1. N번째 원소를 뽑는다(0~N-1번째 원소까지는 정렬이 되어있는 상태) 2. N번째 원소를 0~N-1 사이에 정렬된 위치로 이동시킨다. 3. N+1의 원소에서 1~2번 반복 이렇게 마지막 원소까지 이동하면 정렬이 완료되게 됩니다. 이 알고리즘은 모든 원소를 한번씩 선택(n) 하여 선택된 원소를 정렬된 원소들과 비교(n-1)를 진행하기 때문에 1+2+3+....n-1 = n(n-1)/2 = O(n2)의 시간복잡도를 갖습니다. 이때 n-1번을 모두..

합병정렬 알고리즘은 분할정복방법을 사용한 정렬 알고리즘 입니다. 합병정렬은 정렬을 할 배열을 가장 작은 단위(배열의 Element가 2개만 있을때까지)로 분할하고 분할한 작은 단위의 배열을 정렬하고, 정렬된 배열을 합치고 다시 정렬하는 방법을 사용합니다. 출처 : www.101computing.net/merge-sort-algorithm/ Merge Sort Algorithm | 101 Computing Computers are often used to process large amounts of data. Some of the tasks they can be used for is to sort data sets in order, e.g. numerical order or alphabetical orde..

퀵 정렬은 파이썬의 유명한 Package인 Pandas에서 보셨을 수 도 있습니다. (Pandas DataFrame을 정렬하는 방법중 하나로 쓰입니다) pandas.pydata.org/pandas-docs/version/0.15.2/generated/pandas.DataFrame.sort.html pandas.DataFrame.sort — pandas 0.15.2 documentation columns : object Column name(s) in frame. Accepts a column name or a list for a nested sort. A tuple will be interpreted as the levels of a multi-index. ascending : boolean or lis..