꾸준히하자아자

삽입정렬 삽입정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. + 손 안의 카드를 정렬하는 방법과 같다. 새로운 카드를 정렬된 카드 사이의 알맞은 사이를 찾아 삽입해준다. 두번째 원소부터 시작하여 그 앞 원소들과 비교하여 삽입할 위치를 지정하고 원소를 뒤로 옮기고 그 자리에 원소를 삽입하여 정렬한다. 삽입정렬 GIF 이런식으로 두번째 원소부터 마지막 원소까지 정렬된 앞 원소들과 비교하여 알맞은 위치를 찾아 삽입한다. 역시 gif가 이해가 잘된다... C++로 구현 #include using namespace std; int a[10] = { 3,6,7,1,4,2,9,0,5,8 }; void insertion..

버블 정렬 버블정렬 (bubble sort)란 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간복잡도가 O(n^2)로 상당히 느리지만 코드가 단순하기 때문에 자주 사용된다. (출처 위키백과) GIF 으로 개념이해 오름차순정렬을 하게되면 첫번째 원소와 두번째 원소를 비교하여 첫번째 원소가 두번째 원소보다 크면 두 원소를 교환하고 두번째 원소와 세번째 원소를 비교하고, 세번째 원소와 네번째 원소를 비교하고 이런식으로 (마지막-1) 번째 원소와 마지막 원소를 비교하여 정렬한다. 이런식으로 1번 처음부터 끝까지 수행하게 되면(1회전 후) 배열의 가장 큰 원소가 맨 뒤로 이동하므로 2회전을 수행할때는 맨 끝에 있는 원소는 정렬에서 제외된다. 1회전을 할때 교환이 이루어지지 않으면 정렬이 된 상태라고 볼 수 있는..

선택정렬 선택정렬 (selection sort)은 제자리 정렬 알고리즘의 하나이다. 주어진 리스트 중에 최소값을 찾는다. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)). 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 이 1,2,3을 계속 반복하는 알고리즘이다. 이런식으로 처음엔 첫번째 원소부터 마지막 원소중 최소값을 찾아 배열 맨 앞에 있는 원소와 교환하고 (정렬된 첫번째 원소를 제외한) 두번째 원소부터 마지막 원소중 최소값을 또 찾아 배열 두번쨰 원소와 교환하고 배열 마지막 원소는 자동으로 정렬되기 때문에 원소 개수 -1 만큼 반복해 주면 된다. C++ 로 구현 #include using namespace std; int a[10] = { 3,6,7,1,4,2,9,0,5,8 }..

이후에 추가로 알게된 것들을 계속 추가 할 예정이다. 인프런 강좌 내용을 참고하였습니다, 퀵 정렬 (quick sort) 퀵정렬은 분할정복 방법을 사용합니다. 분할정복방법이란 순환적(recursive)으로 문제를 푸는 하향식(top-down) 접근방법입니다. 분할: 배열을 pivot 을 기준으로 pivot보다 작은 값들과 pivot 보다 크거나 같은 값으로 두 부분으로 나눈다. 정복: 각 부분을 순환적으로 정렬한다. 합병: nothing to do (필요x) 슈도코드 A배열의 첫번째 원소를 p, 마지막 원소를 r로 설정한다. 마지막 수를 pivot으로 뒀을때 그 pivot이 어디에 위치해있는지 구하는 partition 함수를 이용한다. 검사하려는 값이 pivot보다 클때, 결국 오른쪽에 있는 원소들 값이..