Ruby實現merge_sort算法離開輸入數組中的元素

我想實現合併排序功能到我的應用程序。它將一個數組作爲輸入，對它進行排序並輸出排序後的數組。Ruby實現merge_sort算法離開輸入數組中的元素

def sort(list) 
    swapped = true 
    sorted_list = [] 

    slice_count = list.size.to_i 
    chunked_list = list.each_slice(slice_count).to_a.each{ |element| element.fill nil, slice_count, 0 }.transpose.map(&:compact) 

    while swapped do 
    swapped = false 

    (slice_count-1).times do |i| 
     if chunked_list[i][0] > chunked_list[i+1][0] 
     chunked_list[i], chunked_list[i+1] = chunked_list[i+1], chunked_list[i] 
     swapped = true 
     end 
    end 
    break if !swapped 
    end 

    (slice_count-1).times do |i| 
    sorted_list.push(chunked_list[i][0]) 
    end 

    puts "Sorted list (merge): #{sorted_list}" 
end

我的問題來自獲取輸入數組。運行merge.sort（[0，3,8，5,4，9，22]）輸出排序後的數組，而不0和22：Sorted list (merge): [3, 4, 5, 8, 9]

調試並返回在撬的 '列表' 變量給我[3, 4, 5, 8, 9, 22] ，其中包括最終輸出中不存在的22個，但仍然不包括輸入數組中的0元素。爲什麼它沒有采取完整陣列？

來源

2017-03-16 Sam Lim

我有一個問題上是，如果這個功能真的認爲合併排序？在while循環之後，它將數組分解爲[[0]，[3]，[4]，[5]，[8]，[9]，[22]]。不應該將它分解爲2個數組[[0,3,4]，[5,8,9,22]]，以被視爲合併排序？ –

合併排序有兩個問題：1）它是一種冒泡排序，而不是合併排序; 2）一個錯誤的錯誤。 –

正確，但不合並排序分成2，然後3，依此類推，直到每個元素都在它自己的數組中？一旦它們都被分解成單個的塊，你會比較嗎？ @JörgWMittag –

您需要刪除 - 上（slice_count）.times 1做

def sort(list) 
    swapped = true 
    sorted_list = [] 

    slice_count = list.size.to_i 
    chunked_list = list.each_slice(slice_count).to_a.each{ |element| element.fill nil, slice_count, 0 }.transpose.map(&:compact) 

    while swapped do 
    swapped = false 

    (slice_count-1).times do |i| 
     if chunked_list[i][0] > chunked_list[i+1][0] 
     chunked_list[i], chunked_list[i+1] = chunked_list[i+1], chunked_list[i] 
     swapped = true 
     end 
    end 
    break if !swapped 
    end 

    (slice_count).times do |i| 
    sorted_list.push(chunked_list[i][0]) 
    end 

    puts "Sorted list (merge): #{sorted_list}" 
end 

Sorted list (merge): [0, 3, 4, 5, 8, 9, 22]

來源

2017-03-16 19:12:31

這看起來很像泡泡排序，你確定它是合併排序嗎？ –

Ruby實現merge_sort算法離開輸入數組中的元素

回答

相關問題