Algorithm/정렬알고리즘 검색 결과

해당 글 7건

[Algorithm]합병정렬(merge sort) 알고리즘 C++

대표적인 nlogn 정렬 알고리즘중 마지막인 합병(병합)정렬 이다. 합병정렬은 항상 nlogn 의 성능을 내는 알고리즘으로 힙정렬과 같고 최악상황의 퀵(n^2) 보다 안정적이다. 하지만 평균적으로 퀵정렬보다 느린 성능을 보이며 알고리즘 구현에있어 힙정렬보다 메모리를 더 많이먹는다. 합병정렬 -합병정렬을 쉽게 알수있는 짤(위키백과)- 합병정렬은 분할정복알고리즘이다. 분할정복은 하나의 문제를 잘개 쪼개어(분할하여) 문제를 해결하는 방법임. 합병정렬이 대표적인 분할정복을 사용하는 알고리즘인데. 정렬할 배열을 하나의 원소로 쪼개어 비교하며 정렬하는 방법이다. 이 정렬은 두가지 순서만 알면 되는데. 1.분할 (가장 작은 단위까지 분할)2.정렬 (가장 작은 단위부터 정렬) 과정을 정렬이 완료될때까지 반복이다. 순서..
Algorithm/정렬알고리즘 2018. 6. 12. 12:49

[Algorithm]퀵정렬 알고리즘(C++)

시간복잡도가 nlogn 인 정렬 알고리즘은 대표적으로 힙정렬, 병합정렬, 퀵정렬이 있다.힙정렬은 지난번에 알아보았고 이번엔 nlogn 알고리즘중에서도 평균적으로 가장 성능을 잘 내는 퀵정렬에 대해 알아보겠따. [Algorithm]힙정렬 알고리즘(C++) 힙정렬은 시간복잡도가 nlogn 으로 퀵정렬과 병합(합병)정렬과 같은 시간복잡도를 가진 정렬 알고리즘이다. 하지만 병합정렬과는 다르게 추가적인 메모리가 필요하지않고, 항상 nlogn의 정렬 성능을 보여주기때문.. dpdpwl.tistory.com 퀵정렬최악의 경우 n^2의 성능을 내지만 사실 최악의경우는 잘 나오지 않는다.. 이경우를 제외하곤 평균적으로 nlogn 의 성능.대부분의 상황에서 nlogn중 가장빠르다.사실 퀵정렬은 딱히 복잡한게 없다. 정렬을..
Algorithm/정렬알고리즘 2018. 6. 4. 14:29

[Algorithm]힙정렬 알고리즘(C++)

힙정렬은 시간복잡도가 nlogn 으로 퀵정렬과 병합(합병)정렬과 같은 시간복잡도를 가진 정렬 알고리즘이다. 하지만 병합정렬과는 다르게 추가적인 메모리가 필요하지않고, 항상 nlogn의 정렬 성능을 보여주기때문에 최악의 경우 n^2 의 성능을 보이는 퀵정렬보다 안정적인 성능을 보인다. 힙정렬은 힙의 구조에 대해 알고있으면 생각보다 간단한 정렬이다. 힙정렬을 알아보기전에 힙(Heap) 에 대해 간단히 알아보자. 힙(Heap)힙 트리 라고도 하는 힙은 완전이진트리 형태의 자료구조이다. 완전이진트리노드를 삽일할때 왼쪽부터 차례대로 추가하는 이진트리(모든 노드의 차수가 2이하로 구성된 트리) 위와같은 트리가 완전이진트리이며(각노드의 왼쪽부터 채워진 이진트리) 아래는 그냥 이진트리. 힙에는 최소힙과 최대힙이 있으며..
Algorithm/정렬알고리즘 2018. 5. 30. 14:47

[Algorithm]내부정렬 정렬시간(시간복잡도)

안녕하세요. 오늘은 내부정렬(버블정렬,선택정렬,삽입정렬)의 시간복잡도에 대해 알아보겠습니다. 버블정렬과 선택정렬 삽입정렬 모두 시간복잡도는 O(n²) 로 동일한데요. 그럼 과연 난수 배열을 생성하여 정렬을 시작하고 끝나는 시간이 모두 같은지 확인해보겠습니다. 12만개의 난수 배열을 생성하여 정렬시간을 비교해보았습니다. 결과는 거의 모든 상황에서 삽입정렬이 가장 빨리 끝이났고 버블정렬과 선택정렬은 비슷한 시간이 나오는것을 확인할수 있었습니다. 삽입정렬은 최악의 경우 시간복잡도가 O(n²)인 반면 버블정렬과 선택정렬은 항상 모든상황에서 자신만의 정렬 알고리즘을 전부 수행하기때문에 일정한 시간이 나오는데요. 삽입정렬 같은경우 최악의 경우는 잘 나오지 않기때문에 가장 빠르게 끝나버리는것같습니다. 그래서 난수배열..
Algorithm/정렬알고리즘 2017. 8. 24. 17:32

[Algorithm]삽입정렬 예제(insertion sort)

안녕하세요. 이번에도 기본정렬중 하나인 삽입정렬(insertion sort) 에 대해 알아보겠습니다. 삽입정렬은 기준이 되는 인덱스의 앞쪽을 검사하여 기준이 되는 인덱스가 들어갈 자리를 찾아서 삽입? 하는 정렬입니다. 시작은 1번 인덱스로 (0번인덱스가 처음인덱스), 0번 인덱스는 정렬이 되어있다고 하고 시작을합니다.(수가 하나라면 정렬을 할 필요가 없겠죠?) 그림과 예제를 보겠습니다. 보시는 것처럼 기준이 되는 수와 앞쪽 인덱스를 비교하여 앞쪽에 기준이 되는 수보다 큰 값을가진 인덱스가 있으면 한칸 밀고 기준이되는 인덱스의 수를 넣고, 또 앞쪽인덱스와 비교하여 앞쪽 인덱스가 더 크면 한칸밀고 기준이되는 인덱스의 수를 집어넣는 방식입니다. 이렇게 비교인덱스가 -1(0이 끝이기때문) 이 되거나 기준이 되는..
Algorithm/정렬알고리즘 2017. 8. 22. 13:46

[Algorithm]선택정렬 예제(selection sort)

안녕하세요~~~ 오늘은 자바로 선택정렬(selection sort) 에 대해 알아 보겠습니다. 버블정렬과 함께 정렬중에 기본인 선택정렬인데요!! 버블정렬과 마찬가지로 느린 정렬에 속합니다. 하지만 정렬에 기본이되기때문에 알아두면 좋은데요. 선택정렬은 기준이되는 수와 나머지수를 비교하여 가장 낮은수를 제일 앞으로 보내는 정렬입니다!!(오름차순일 경우) 그림설명을 보고 코드를보며 알아보겠습니다. 그림과 같이 0번째 인덱스와 그뒤의 값을 비교한뒤 가장 낮은 값을 0번째로 만들고 수행이 끝났으면 기준을 한칸 옮겨서 똑같이 수행합니다. 코드로 보면 public class SelectSort { public static void main(String[] args) { int[] a = {254,3,213,64,75..
Algorithm/정렬알고리즘 2017. 8. 22. 10:51

[Algorithm]버블정렬 예제(bubble sort)

안녕하세요~~~ 오늘은 자바로 버블정렬에 대해 알아보겠습니다. 버블정렬은 정렬중에 가장 기본적? 인 정렬 방법으로 정렬 대상의 n번째 인덱스와 n+1번째 인덱스를 비교하여 큰값을 뒤로 보내는 방법입니다. 그림설명을 보고나서 바로 코드를 보며 알아보겠습니다. public class BubbleTest { public static void main(String[] args) { int[] a = {254,3,213,64,75,56,4,324,65,78,9,5,76,3410,8,342,76}; int b; for(int i = 0 ; i a[j+1]) { b = a[j]; a[j..
Algorithm/정렬알고리즘 2017. 8. 11. 22:26