การเรียงลำดับแบบค็อกเทลเชกเกอร์

การเรียงลำดับแบบค็อกเทลเชกเกอร์

ประเภท	Sorting algorithm
โครงสร้างข้อมูล	Array
ประสิทธิภาพเมื่อเกิดกรณีแย่ที่สุด	$O(n^{2})$
ประสิทธิภาพเมื่อเกิดกรณีดีที่สุด	$O(n)$
ประสิทธิภาพเมื่อเกิดกรณีทั่วไป	$O(n^{2})$
ปริมาณความต้องการพื้นที่เมื่อเกิดกรณีแย่ที่สุด	$O(1)$

การเรียงลำดับแบบค็อกเทลเชกเกอร์ ยังเป็นที่รู้จักกันในนามฟองเรียงลำดับ เรียงระลาดเรียงสับเปลี่ยน หรือกระสวยเรียงเป็น รูปแบบของฟองสบู่ที่มีทั้งแบบอัลกอริทึมการจัดเรียงที่มีเสถียรภาพและการเรียงลำดับการเปรียบเทียบ อัลกอริทึมจะแตกต่างจากการจัดเรียงแบบฟองสบู่ในแบบที่เรียงตามทั้งสองทิศทางในแต่ละการผ่านรายการ อัลกอริทึมการเรียงลำดับนี้เป็นเพียงเล็กน้อยยากที่จะใช้มากกว่าการเรียงลำดับฟองและแก้ปัญหาของเต่าในฟองสบู่ จะให้การปรับปรุงประสิทธิภาพเพียงเล็กน้อยและไม่เพิ่มประสิทธิภาพการทำงานแบบไม่ประจำตัว เช่นการเรียงลำดับฟองสบู่ก็ไม่ได้เป็นที่น่าสนใจในทางปฏิบัติ (การจัดเรียงแทรกเป็นที่ต้องการสำหรับประเภทที่เรียบง่าย) แม้ว่าจะพบว่ามีประโยชน์บางอย่างในด้วย

การเรียงลำดับแบบค็อกเทล ชาร์คเกอร์ ซอร์ต  เป็นการปรับปรุงรูปแบบการจัดเรียงแบบ Bubble sort ให้ทำงานได้ดีขึ้น ด้วยการเพิ่มขึ้นตอนการจัดเรียงขึ้นอีกกระบวนการหนึ่ง โดยวิธีการจัดเรียงสองทางสลับกัน

ซูโดโค้ด
procedure cocktailShakerSort( A : list of sortable items ) defined as:
  do
    swapped := false
    for each i in 0 to length( A ) - 2 do:
      if A[ i ] > A[ i + 1 ] then // test whether the two elements are in the wrong order
        swap( A[ i ], A[ i + 1 ] ) // let the two elements change places
        swapped := true
      end if
    end for
    if not swapped then
      // we can exit the outer loop here if no swaps occurred.
      break do-while loop
    end if
    swapped := false
    for each i in length( A ) - 2 to 0 do:
      if A[ i ] > A[ i + 1 ] then
        swap( A[ i ], A[ i + 1 ] )
        swapped := true
      end if
    end for
  while swapped // if no elements have been swapped, then the list is sorted
end procedure

ช่องทางด้านขวาแรกจะเปลี่ยนองค์ประกอบที่ใหญ่ที่สุดไปยังตำแหน่งที่ถูกต้องในตอนท้ายและทางออกด้านซ้ายต่อไปนี้จะเปลี่ยนองค์ประกอบที่เล็กที่สุดไปยังตำแหน่งที่ถูกต้องในตอนเริ่มต้น การส่งผ่านครั้งที่สองเสร็จสมบูรณ์จะเปลี่ยนองค์ประกอบที่เล็กที่สุดเป็นอันดับสองและใหญ่เป็นอันดับสองไปยังสถานที่ที่ถูกต้องและอื่น ๆ หลังจากที่ฉันผ่านฉัน i แรกและองค์ประกอบ i ล่าสุดในรายการอยู่ในตำแหน่งที่ถูกต้องและไม่จำเป็นต้องได้รับการตรวจสอบ โดยการย่อส่วนของรายการที่เรียงลำดับในแต่ละครั้งจำนวนการดำเนินการสามารถลดลงครึ่งหนึ่ง (ดูการจัดเรียงแบบฟอง)

นี่เป็นตัวอย่างของอัลกอริธึมใน ภาษาไพตรอน โดยมีการเพิ่มประสิทธิภาพในการจดจำดัชนีการแลกเปลี่ยนล่าสุดและการอัปเดตขอบเขต

def cocktail_shaker_sort(array):
  
    for i in range(len(array)-1, 0, -1):
        swapped = False
		
        for j in range(i):
            if array[j] > array[j+1]:
                array[j], array[j+1] = array[j+1], array[j]
                swapped = True
		print(array)
		
        for j in range(i, 0, -1):
            if array[j] < array[j-1]:
                array[j], array[j-1] = array[j-1], array[j]
                swapped = True
		print(array)

        
        
        if not swapped:
            return array
            
if __name__ == '__main__':
    user_input = raw_input('Enter numbers Ex.[1,0,8,9]:\n').strip()
    array = [int(x) for x in user_input.split(',')]
    print(cocktail_shaker_sort(array))

ความแตกต่างจากการจัดเรียงแบบฟองสบู่

เป็นรูปแบบเล็กน้อยของการจัดเรียงฟองสบู่ มันแตกต่างจากที่แทนซ้ำ ๆ ผ่านรายการจากด้านล่างไปด้านบนจะผ่านสลับจากด้านล่างขึ้นบนและจากบนลงล่าง สามารถทำได้ดีกว่าฟองสบู่มาตรฐานเล็กน้อย เหตุผลในการนี้คือการจัดเรียงแบบฟองสบู่เท่านั้นผ่านรายการไปในทิศทางเดียวและดังนั้นจึงสามารถย้ายรายการย้อนหลังได้ทีละขั้นตอนเท่านั้น

ตัวอย่างของรายการที่พิสูจน์จุดนี้คือรายการ (2,3,4,5,1) ซึ่งจะต้องผ่านการจัดเรียงค็อกเทลหนึ่งครั้งเพื่อจัดเรียง แต่ถ้าใช้การจัดเรียงฟองแบบเรียงจากน้อยไปมากจะใช้เวลาสี่ ผ่าน อย่างไรก็ตามการจัดเรียงค๊อกเทลแบบหนึ่งจะต้องนับเป็นแบบฟองสบู่สองแบบ โดยทั่วไปแล้วการจัดเรียงค็อกเทลจะเร็วกว่าการจัดเรียงแบบฟองสบู่น้อยกว่าสองเท่า

การเพิ่มประสิทธิภาพอีกอย่างหนึ่งอาจเป็นได้ว่าอัลกอริทึมจะจำตำแหน่งที่ได้รับการแลกเปลี่ยนจริงครั้งล่าสุด ในการทำซ้ำถัดไปจะไม่มีการแลกเปลี่ยนใดที่เกินขีด จำกัด นี้และอัลกอริทึมจะมีการส่งผ่านที่สั้นกว่า เนื่องจากการจัดเรียงเครื่องปั่นค็อกเทลจะเกิดขึ้นแบบสองทิศทางช่วงของการแลกเปลี่ยนที่เป็นไปได้ซึ่งเป็นช่วงที่จะทดสอบจะลดลงต่อ pass ซึ่งช่วยลดเวลาในการทำงานโดยรวมเล็กน้อย

ความซับซ้อน

ความซับซ้อนของเครื่องปั่นค็อกเทลในสัญกรณ์ O ใหญ่คือ {\ displaystyle O (n ^ {2})} O (n ^ {2}) สำหรับทั้งกรณีที่เลวร้ายที่สุดและกรณีค่าเฉลี่ย แต่มันกลายเป็นใกล้ชิดกับ {\ displaystyle O (n)} O (n) ถ้ารายการถูกสั่งซื้อส่วนใหญ่ก่อนที่จะใช้อัลกอริทึมการเรียงลำดับ ยกตัวอย่างเช่นถ้าทุกองค์ประกอบอยู่ในตำแหน่งที่แตกต่างจาก k (k ≥ 1) จากตำแหน่งที่มากที่สุดก็จะสิ้นสุดลงความซับซ้อนของการเรียงลำดับค๊อกเทลกลายเป็น {\ displaystyle O (kn)} {\ displaystyle O (kn).}

การเรียงลำดับเครื่องปั่นค็อกเทลยังกล่าวสั้น ๆ ในหนังสือศิลปะการเขียนโปรแกรมคอมพิวเตอร์พร้อมกับการปรับแต่งฟองแบบคล้าย ๆ กัน สรุปได้ว่า Knuth ได้กล่าวถึงการเรียงลำดับฟองและการปรับปรุง:

แต่ไม่มีการปรับแต่งเหล่านี้นำไปสู่อัลกอริทึมที่ดีกว่าการแทรกตรง (นั่นคือการจัดเรียงแบบแทรก); และเรารู้อยู่แล้วว่าการแทรกตรงไม่เหมาะสำหรับ N ขนาดใหญ่ [... ] ในระยะสั้นการจัดเรียงฟองดูเหมือนว่าไม่มีอะไรจะแนะนำให้ใช้ยกเว้นชื่อที่จับใจและความจริงที่ว่ามันนำไปสู่ปัญหาทางทฤษฎีบางอย่างที่น่าสนใจ