늘 겸손하게

출처 : https://www.geeksforgeeks.org/graph-and-its-representations/ Graph and its representations - GeeksforGeeks A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions. www.geeksforgeeks.org 안녕하세요 besforyou 입니다 이번 글에서는 그래프 알고리즘 문제들을 풀기 위한 기초에 ..

안녕하세요 이번 글에는 정렬 알고리즘들의 정렬 속도 차이를 비교해볼까 합니다. 비교할 정렬 알고리즘은 1. 버블 정렬 (bubble sort) 2. 단순 삽입 정렬(straight insertion sort) 3. 퀵 정렬(quick sort) 입니다. 정렬 알고리즘 구현 코드는 글 하단에 있습니다 :) - 기본 지식 버블 정렬과 단순 삽입 정렬의 시간 복잡도는 O(n^2), 퀵 정렬의 시간 복잡도는 O(n logn)입니다. 정렬 알고리즘들의 실제 정렬 속도 차이를 알기 위해 라이브러리 의 함수인 clock()을 이용해 정렬 전 시간과, 정렬 후 시간을 비교할 것입니다. 또한 무작위 숫자가 저장된 배열을 만들기 위해 라이브러리 의 rand() 함수도 사용할 것입니다. 또한 정렬할 원소 수가 적을 경우와 ..

Quick sort ( 퀵 정렬 ) 가장 빠른 정렬 알고리즘 중 하나로 빠른 정렬 속도 덕에 널리 쓰입니다. C/C++ 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 void quick_sort(int a[], int left, int right) { int pl = left; int pr = right; int x = a[(pl+pr)/2]; do { while(a[pl] x) pr--; if (pl

단순 삽입 정렬은 요약하자면 정렬되지 않은 부분의 첫 번째 요소를 정렬된 부분의 알맞은 위치에 삽입하는 정렬 알고리즘입니다. 아래와 같은 배열을 예로 들어보겠습니다. 6 3 2 1 5 9 10 단순 삽입 정렬은 2번째 요소부터 시작합니다. 2번째 요소인 3을 알맞은 위치에 배치하면 6 3 2 1 5 9 10 바로 앞 숫자인 6과 자리가 바꾸어집니다. 3 6 2 1 5 9 10 다음으로 3번째 요소인 2를 알맞은 위치에 배치하면 3 6 2 1 5 9 10 앞자리에 위치하던 3과 6이 뒤로 밀리고 2가 앞으로 오게됩니다. 2 3 6 1 5 9 10 이후에도 이와 같은 작업을 4번째 요소, 5번째 요소, ... , N - 1 번째 요소까지 반복하여 정렬을 마치게 됩니다. 이를 코드로 구현하려면 윗 문장의 '이..