정렬 알고리즘?

따라서 "정렬 알고리즘이 정확히 무엇입니까?"가 궁금할 것입니다. 음, 정렬 알고리즘은 단순히 주어진 배열이나 일부 요소 목록을 오름차순 또는 내림차순으로 재정렬하는 데 사용됩니다. 데이터 구조에서 요소의 새 순서를 결정하는 비교 연산자를 사용합니다.

예를 들어 정렬되지 않은 숫자의 배열이 있는 경우 알고리즘에서 오름차순으로 정렬하기를 원했습니다.

[3,5,7,1,2] => [1,2,3,5,7]

버블 정렬

이제 버블 정렬 알고리즘은 이해하기 가장 간단한 정렬 알고리즘 중 하나입니다. 버블 정렬은 인접한 요소의 순서가 잘못된 경우 반복적으로 교체하여 작동합니다. 배열에서 가장 작은 것에서 가장 큰 것으로 오름차순이라고 가정해 봅시다.

여기에서 정확히 무슨 일이 일어나고 있습니까?

여기서 버블 정렬 알고리즘이 수행하는 작업은 모든 단일 반복을 통해 각 정수 쌍을 지속적으로 비교하여 코드를 설계하는 방법과 관련하여 두 정수를 배치할 위치를 결정하는 것입니다. 위의 예에서는 가장 작은 것부터 큰 것까지 오름차순으로 정렬합니다.

의사 코드

다음은 __bubble 정렬 알고리즘을 구현하는 방법을 시작하기 위한 몇 가지 단계입니다.

먼저 배열을 받는 bubbleSort라는 함수를 만듭니다.

for 루프를 사용하여 배열의 끝에서 시작까지 변수 i를 사용합니다.

처음에서 시작하여 i - 1로 끝나는 변수 j가 있는 내부 루프 사용.

arr[j]가 arr[j + 1]보다 큰 경우 두 값을 교환합니다.

끝에 정렬된 배열을 반환합니다

.

코드

function bubbleSort(arr){
  for(let i = arr.length - 1; i > 0; i++){
    for(let j = i -1; j < arr.length; j++){
      if(arr[j] > arr[j + 1]){
        var temp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = temp
      }
    }
  }
  return arr
}

이 코드를 잘 살펴보면 아직 끝나지 않았습니다! 데이터가 거의 정렬되었거나 이미 정렬된 시나리오에서는 다시 정렬할 필요가 없습니다. 그러나 현재 버블 정렬 알고리즘은 배열이 어느 정도 또는 이미 존재하는지 여부를 고려하지 않습니다. 길이가 32 이상인 배열이 있는 경우 이러한 종류의 논리는 불필요한 공간을 차지합니다.

이를 방지하기 위해 코드 내에서 "여기서 스왑을 수행했습니까?"라고 묻는 검사를 수행할 수 있습니다. 그렇지 않은 경우 반복을 완료해야 합니다.

최적화

따라서 불필요한 스와핑이 발생하지 않도록 이 코드를 최적화하기 위해 부울을 받는 noSwaps 변수를 사용할 수 있습니다.

function bubbleSort(arr){
  var noSwaps;
  for(let i = arr.length - 1; i > 0; i++){
    noSwaps = true
    for(let j = i -1; j < arr.length; j++){
      console.log(arr, arr[j], arr[j + 1])
      if(arr[j] > arr[j + 1]){
        var temp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = temp
        nSoSwaps = false
      }
    }
    if(noSwaps) break
  }
  return arr
}

여기서 반복 내에서 더 이상 스왑이 없으면 코드에서 벗어나 배열을 반환해야 합니다. 이것은 가능한 스왑을 위해 영역을 반복하는 코드의 불필요한 작업을 제거합니다.

결론

이것으로 버블 정렬에 대한 블로그를 마칩니다! 선택 정렬에 초점을 맞춘 다음 블로그를 기대해 주세요.