JavaScript 거품 정렬 최소 행

나는 컴퓨터 과학 학위를 받지 못해서 일정 시간마다 컴퓨터 과학 개념을 배운다.나는 인터뷰에서 기포 정렬에 대한 질문을 받았기 때문에 자바스크립트로 작성하기로 결정했다.

기포 정렬은 어떻게 작동합니까?


기본적으로 거품 정렬 함수는 수조를 두루 돌아다니며 모든 값을 오른쪽의 이웃과 비교하고 이웃이 비교적 작으면 교환한다.그것은 교환할 수 있는 것이 없을 때까지 끊임없이 진열 속을 뚫고 지나갔다.
이렇게 보여요.
Start: [9,6,3,2,4]
After 1: [6,3,2,4,9]
After 2: [3,2,4,6,9]
After 3: [2,3,4,6,9]
After 4: [2,3,4,6,9]
왜 그것은 세 번째 이후에 정확한 순서가 있지만 네 번을 겪었습니까?
네 번째 운행이 되어서야 주문이 정확하고 교환할 필요가 없다는 것을 알았기 때문이다.
그래서 나는 간단한 함수를 하나 썼다.
function bubble(arr){
  do { 
    var swaps = false; 
    arr.forEach((val, ind) => {
      if (val > arr[ind + 1]) {
        swaps = true; 
        arr[ind] = arr[ind + 1];
        arr[ind + 1] = val;
      } 
    });
  } while (swaps == true);
  return arr;
}

이것은 가장 짧은 기포 정렬입니까?


그것은 성공했다.가능한 한 적은 코드 줄로 작성할 수 있도록 확보하고 싶습니다.내가 구글에서'javascript most efficient bubble sort'을 검색했을 때, 앞의 두 결과는 2-3줄을 더 검색해야 했다.
세 가지로 귀결된다.
1. 그들은 for 을 사용하여 수조를 순환하고 나는 Array.prototype.forEach() 을 사용한다.forEach 방법은 모든 원소를 조작하는 리셋 함수에 이 원소의 값, 색인, 심지어 수조 자체를 제공한다.그래서 코드 한 줄을 저장했습니다.
그들이 값을 교환해야 할 때, 그 값을 저장하기 위해 임시 값을 설명해야 하지만, 나는 함수의 매개 변수로 값을 제공했다.
값과 인덱스 번호의 코드(예: valind)를 가져옵니다.
if (val > arr[ind + 1]) { 
  swaps = true; 
  arr[ind] = arr[ind + 1]; 
  arr[ind + 1] = val;
}
인덱스 번호만 가져오는 코드(예: i):
if (arr[i] > arr[i + 1]) { 
  swaps = true; 
  let temp = arr[i + 1]; 
  arr[i + 1] = arr[i]; 
  arr[i] = temp;
}
2. for 순환을 만들기 전에 그들은 수조의 길이로 변수를 설명했는데 forEach은 단지 알고 있을 뿐이다.
그 중 하나는 swaps 순환에서 do... while 키워드로 let블의 값을 표시합니다.나와 다른 사람은 var으로 순환 내에서 그것을 성명했다.let 키워드는 블록 범위이기 때문에 순환 내에서 변수를 설명하면 순환 컨트롤러가 보이지 않습니다.var 키워드는 함수 범위이기 때문에 성명과 분배 후 순환 중의 어느 위치에서든 볼 수 있습니다.let을 사용하면 가독성을 현저하게 향상시키지 못하고 불필요한 복잡성을 증가시켰다(이 예에서).

좋아, 그것은 비교적 짧지만, 내 것이 더 좋니?


나는 나 자신에 대해 매우 만족하지만, 나는 이미 forEach의 균형을 사용하는 것을 알고 있다.
일단 시작하면 forEach은 패턴을 통해 전체 순환을 완성해야 합니다.for 순환은 return 또는 break 키워드를 사용하여 미리 종료하거나 continue을 사용하여 처리를 끝내고 다음 교체로 넘어갈 수 있습니다.forEach 방법에는 이런 것이 없다.for 순환의 장점은 거품 정렬이 모든 값을 교체해야 한다는 것이다. 거의.
마지막 값을 마지막 색인에 1을 더한 정의되지 않은 값과 비교할 필요가 없습니다.for 순환을 마지막 값을 제외한 모든 값으로 설정할 수 있습니다. 이것은 순환 중의 코드 운행 횟수가 한 번 줄었다는 것을 의미합니다.
우승자: for바퀴.
또 다른 문제는 진열의 길이를 확정하는 두 가지 방법의 비교 효율이다.
내부에서 forEach은 기본적으로 for 순환을 실행하고 매번 교체할 때마다 그룹의 길이를 찾습니다.for 순환 변체에서 수조 길이는 변수에 한 번 설정한 다음 이 변수를 순환해서 사용합니다.
만약 수조의 길이가 순환 과정에서 변화할 수 있다면, 예를 들어 Array.prototype.splice 방법으로 중복 항목을 삭제하면, 순환의 매번 교체에서 그것을 찾는 것이 매우 유용하다.
그러나 수조의 크기가 변하지 않는 곳에서는 한 번만 수조의 길이를 얻고 변수에 넣어 for을 순환하여 사용할 수 있다. 이것은 엔진에 달려 있는 것 같다.V8(Chrome, node.js)에서 찾기는 사실상 좀 빠른 것 같지만 다른 엔진인 YMMV를 사용했다.
우승자: 우리 무승부로 합시다.
마지막으로 letvar의 사용에 관해서는 사실상 하나의 문제이다. 한 문장에서 한 번 + 중복 부여가 한 문장에서 중복 성명과 부여보다 빠른지 여부이다.
그래서 나는 이 두 가지 방법에 대해 시간을 재어 여러 테스트에서 각각 100억 회를 운행했다.var 성명과 부치 방법은 매번 테스트에서 0.2% 정도의 우세로 이겼다.이것은 아직 승자가 되기에는 부족하다.
우승자: 우리도 무승부로 합시다.

스택 오버플로우 토론 그럼, 내 것이 더 좋아요?


내 코드는 더욱 짧고 가독성이 강하지만 순환을 통과할 때마다 비교 코드의 전체 실행을 뛰어넘는 것은 for 순환의 결정적인 장점이다.그러므로'더 좋다'...그래, 너의 우선순위에 달려 있다.

좋은 웹페이지 즐겨찾기