개발자's Life

버블정렬 : 인접 요소끼리 Swap 연산을 수행하며 정렬을 한다. 오름차순, 내림차순에 따라 작은값의 위치가 달라지고 인덱스 0 ~ N 까지 비교 후 제일 마지막 인덱스 N 이 정해진 뒤 다시 0 ~ N -1 까지 비교 후 N - 1 인덱스에 값이 정해진다. 이러한 작업들이 반복이 되고 N을 N 번 비교하여 시간복잡도는 N제곱이다. 2023.07.29 - [코딩테스트/Study] - [알고리즘] 로직이 단순한 버블정렬의 개념 [알고리즘] 로직이 단순한 버블정렬의 개념 버블 , 선택, 삽입, 퀵, 병합, 기수 정렬 버블정렬 인접 요소끼리 swap 연산을 수행하며 정렬 정렬 알고리즘보다 속도가 느리면 로직이 단순한 정렬 알고리즘 이다. 오름차순으로 정렬시 인접요소 rowen.tistory.com 선택정렬 :..

기수정령의 개념과 원리 _ by.하루코딩,copy RowenJobs 값을 비교하지 않는 특이한 정렬이고 자릿수를 정한 다음 해당 자릿수만 비교한다. 시간 복잡도는 kn 이고 k 는 자릿수 시간복잡도가 가장 짧은 정렬이다. 큐를 만들어 넣는 부분이 좀 어려워질수 있다. 기수정렬은 10개의 큐를 이용 한자릿수에 올 수 있는 자릿수는 0 ~ 9 라 10개의 큐를 이용 일의 자리를 정렬을 하고 ~ N 의 자리까지 큐에 넣어 정렬을 한다. 아래는 강의 예시를 참고해서 확인하면 된다. 첫번째 이미지는 일의 자릿수에 대해 큐에 넣고 순서대로 정렬한 이미지 이고 두번째 이미지는 1차적으로 정렬한 배열의 각 십의자리에 대해 큐에 넣고 그대로 정렬을 한 이미지 이다. 큐는 선입선출의 규칙을 가지고 있어 먼저 들어온 데이터..

병합정렬 장점 안정적이고 시간복잡도도 좋은 알고리즘이고 코딩테스트에서 병합정렬을 이해하고 응용해서 푸는 문제가 많이 나온다. 이 말은 정렬 관련 문제뿐만 아니라 정렬 아이디어를 가지고 푸는 문제도 많이 나온다는 말이다. 핵심은 2개의 그룹을 병합하는 원리는 꼭 숙지 해야한다는 것이다! 투포인터 개념을 사용하여 왼쪽 오른쪽 그룹을 병합하는 것이고 아래 예를 들어 설명을 적어 놓는다. 오름차순으로 정렬! 12 53 27 11 5 23 76 67 병합 정렬은 우선 두개씩 그룹으로 합쳐지며 정렬이 된다.(N번) 4개로 나눠진 그룹을 각각 작은값을 왼쪽 큰 값을 오른쪽으로 정렬이 되고 그룹으로 합쳐지면서 정렬이 일어난다. 12 53 11 27 5 23 67 76 오름차순이기에 작은 값이 앞으로 오게된다. 0번 인..

하나의 기준을 중심으로 계속 데이터를 2개의 집합으로 나누면서 정렬하는것이 핵심이다. 기준이 되는 pivot 과 start 가 가리키는 데이터, end 가 가리키는 데이터를 비교하게 되는데 pivot end : 왼쪽으로 한칸 포인터 이동 pivot > start : 그 자리에서 멈추어 end 포인터를 기다림(또는 기다린 end 포인터 자리와 swap) pivot < end : 그 자리에서 멈추어 start 포인터를 기다림(또는 기다린 start 포인터 자리와 swap) swap 후 start 는 오른쪽, End 는 왼쪽으로 1칸씩 이동 start 와 end 가 만날때까지 반복하고 만나는 지점에서 가리키는 데이터를 비교하여 pivot 이 더 크면 만..

삽입정렬 시간복잡도는 n제곱으로 느린 편이지만 구현하기 쉽다. 코테에서 굳이 많이 사용하진 않지만 코딩인터뷰 관련하여 정렬에 대해 질문 대비하여 알아놓으면 좋다. 예시 설명 ) 5개의 배열이 있고 오름차순으로 정렬을 할려고 한다. 정렬된 데이터 범위 내에서 적절한 위치에 삽입하는 것이 삽입정렬의 핵심이다. 1. 우선 1 인덱스의 값 52의 이전 인덱스 범위를 바라본다 23 52 32 12 45 52 와 23 을 비교할때 52가 크기 때문에 변함이 없고 다음으로 넘어간다. 2. 2 인덱스인 32 가 기준이 되고 그 이전 범위 포함하여 0 - 2 인덱스를 비교한다. 23 52 32 12 45 32는 52보다 작기 때문에 52를 2 인덱스로 옮겨가고 32가 1 인덱스 자리로 넘어가게 된다. (23은 32보다 ..

선택정렬은 알고리즘 문제에 많이 적용되지는 않지만 어떤 문제 일부로 사용이될 수도 있고 기술면접 같은데서 필요할 경우가 있을수도 있다. 선택정렬 알고리즘은 간단하고 버블정렬과 동일하게 시간이 많이 걸린다. 버블정렬과 동일하게 시간이 많이 걸림 (N제곱) 내림차순, 오름차순에 따라 방식이 좀 다르다. 오름차순일 경우 배열 전체에서 최솟값을 계속 찾아 제일 왼쪽으로 쌓아 나간다. 52 3 23 12 최솟값 3과 맨 왼쪽에 있는 52 swap ▽ 3 52 23 12 인덱스 0을 제외한 최솟값 12와 맨 왼쪽에 있는 52 swap ▽ 3 12 23 52 최솟값 23이 이미 맨 왼쪽에 있어 유지가 되고 그 다음 인덱스로 넘어간다 ▽ 3 12 23 52 마지막 인덱스인 값만 남아서 그대로 유지가 되고 위와 같이 배..