Golang의 대체 정렬

이 기사에서는 go 프로그래밍 언어를 사용하여 문제를 해결하고 코드에서 사용할 지원 패키지는 문자열, 배열 등을 정렬하는 데 유용한 golang의 정렬 패키지입니다.

문제

정수 배열이 주어지면 첫 번째 요소가 첫 번째 최대 숫자이고 두 번째 요소가 첫 번째 최소 숫자가 되는 식으로 배열을 인쇄합니다.

예

Input : arr[] = {6, 3, 1, 2, 4, 5, 7}
Output : 7 1 6 2 5 3 4

Input : arr[] = {1, 6, 9, 4, 3, 7, 8, 2}
Output : 9 1 8 2 7 3 6 4

필요한 순서대로 숫자를 인쇄할 수 있는 두 가지 방법이 있습니다.

간단한 해결책은 먼저 최대 요소를 인쇄한 다음 최소값, 두 번째 최대값 등을 인쇄하는 것입니다. 이 접근법의 시간 복잡도는 O(n2)입니다.

효율적인 솔루션에는 다음 단계가 포함됩니다.

그래서 우리는 이것에서 효율적인 솔루션을 구현할 것입니다.

접근하다

O(n Log n) 알고리즘을 사용하여 입력 배열을 정렬합니다.

두 개의 포인터를 유지 관리합니다. 하나는 처음부터, 다른 하나는 정렬된 배열의 끝부터입니다. 또는 두 개의 포인터가 가리키는 요소를 인쇄하고 서로를 향해 이동합니다.

/* 
Alternative sorting problem
EXAMPLE
Input : arr[] = {6, 3, 1, 2, 4, 5, 7}
Output : 7 1 6 2 5 3 4
Input : arr[] = {1, 6, 9, 4, 3, 7, 8, 2}
Output : 9 1 8 2 7 3 6 4
*/
package main
import (
    "fmt"
  "sort"
)
func alternativeSorting(arr []int) {
  sort.Ints(arr)
  fmt.Println("Sorted Array",arr)
  left := 0
  right := len(arr)-1
  for left < right {
     fmt.Printf("%d %d ",arr[right],arr[left])
     left++
     right--
  }
  if len(arr) % 2 != 0 {
    fmt.Printf("%d ",arr[left])
  }
}

func main() {
  arr := []int{12, 1, 6, 4, 7, 10}
  fmt.Println("Before",arr)
  alternativeSorting(arr)
  fmt.Println()
}

산출:

Before [1 12 4 6 7 10]
Sorted Array [1 4 6 7 10 12]
12 1 10 4 7 6

이러한 유형의 콘텐츠를 보려면 my personal blog을 방문하십시오.

읽어 주셔서 감사합니다