퀵정렬에 대해 정리한 게시글!

퀵 정렬이란?

문제

퀵정렬을 사용해서 내가 원하는 값의 인덱스를 출력해내라!

조건

입력 값을 총 두번 받는다.
1번 : 내가 찾고자하는 값 입력
2번 : 무작위의 숫자값 입력(배열로 담는다.)

해결 방법 (생각)

입력 값 두번 받고, 하나의 피벗을 정해서 작은 것은 왼쪽, 큰것은 오른쪽으로 간다.

맘대로 숫자를 입력해서 입력한 숫자를 array 로 입력받는다
내가 찾고자 하는 숫자를 입력한다.
그 방법을 quick sort 하고 정렬된 값에서 찾기!

정렬하는 그 과정에서 전에 찾고자 하는 숫자의 위치의 인덱스를 먼저 출력하고 정렬하도록 하자!

찾고자 하는 숫자의 위치를 인덱스로 출력해라
숫자 를 맘대로 입력 해서 array로

for 문과 if 문을 이용해서 작성을 해봐라!

quick sort 로 만들어서 코드를 만들어봐라

  // 입력 값 1 : 찾고자하는 값
  var inputA = 3; 
  // 입력 값 2 : 배열을 입력한다.
  var arr = [3, 4, 2, 5, 1];

  // 피벗 변수 선언 (우선 제일 낮은 부분)
  var pivot = arr[0];

  // 피벗 보다 높은 배열
  var arrayOfHigh = [];

  // 피벗 보다 낮은 배열
  var arrayOfLow = [];

  // 새로운 피벗 배열
  var arrayOfPivot = [];


  // 퀵정렬된 배열
  var sorted = [];

  // 퀵정렬
    // 입력한 배열의 크기만큼 반복한다. 5의 크기만큼
  for(let i = 0; i < arr.length; i++){  
    // 만약에 피벗보다 작으면 왼쪽 배열 push
    if(pivot < arr[i + 1]) {
      arrayOfLow.push(arr[i + 1]);
    } else if(pivot > arr[i + 1]){
      // 피벗보다 크면 오른쪽 배열 push
      arrayOfHigh.push(arr[i + 1]);
    } else {
      arrayOfPivot.push(arr[i + 1]);
    }
  }

 // quickSort 저장
sorted = arrayOfLow.concat(arrayOfPivot).concat(arrayOfHigh);
 
// 퀵 정렬 출력
console.log(sorted);
// 입력한 값의 인덱스 값 출력
console.log(sorted.indexOf(inputA));

피드백

문제의 접근을 조금 더 깊게 생각해야한다.

피벗된 왼쪽, 오른쪽 배열도 다시 퀵 정렬을 해줘야하는데, 그 부분에 대한 코드는 없다.

재귀함수도 물론 들어가야하고, 2중 for문을 사용해야지 완벽한 퀵정렬 코드가 가능하다.

피드백 후 코드 작성

작성중..