โครงสร้างข้อมูลและอัลกอริทึม - การจัดเรียงเชลล์

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

อัลกอริทึมนี้ใช้การจัดเรียงการแทรกในองค์ประกอบที่กระจายอยู่ทั่วไปก่อนอื่นเพื่อเรียงลำดับจากนั้นจึงจัดเรียงองค์ประกอบที่มีระยะห่างน้อยกว่า ระยะห่างนี้เรียกว่าinterval. ช่วงเวลานี้คำนวณตามสูตรของ Knuth เป็น -

สูตรของ Knuth

h = h * 3 + 1
where −
   h is interval with initial value 1

อัลกอริทึมนี้ค่อนข้างมีประสิทธิภาพสำหรับชุดข้อมูลขนาดกลางเนื่องจากความซับซ้อนโดยเฉลี่ยและกรณีที่เลวร้ายที่สุดของอัลกอริทึมนี้ขึ้นอยู่กับลำดับช่องว่างที่รู้จักกันดีคือΟ (n) โดยที่ n คือจำนวนรายการ และความซับซ้อนของพื้นที่กรณีที่เลวร้ายที่สุดคือ O (n)

การเรียงลำดับเชลล์ทำงานอย่างไร

ให้เราพิจารณาตัวอย่างต่อไปนี้เพื่อให้ทราบว่าการจัดเรียงเชลล์ทำงานอย่างไร เราใช้อาร์เรย์เดียวกับที่เราใช้ในตัวอย่างก่อนหน้านี้ สำหรับตัวอย่างและความเข้าใจง่ายของเราเราใช้ช่วงเวลา 4 สร้างรายการย่อยเสมือนของค่าทั้งหมดที่อยู่ในช่วงเวลา 4 ตำแหน่ง ค่าเหล่านี้คือ {35, 14}, {33, 19}, {42, 27} และ {10, 44}

เราเปรียบเทียบค่าในแต่ละรายการย่อยและสลับค่า (ถ้าจำเป็น) ในอาร์เรย์เดิม หลังจากขั้นตอนนี้อาร์เรย์ใหม่ควรมีลักษณะดังนี้ -

จากนั้นเราใช้ช่วงเวลา 1 และช่องว่างนี้จะสร้างรายการย่อยสองรายการ - {14, 27, 35, 42}, {19, 10, 33, 44}

เราเปรียบเทียบและสลับค่าในอาร์เรย์เดิมหากจำเป็น หลังจากขั้นตอนนี้อาร์เรย์ควรมีลักษณะดังนี้ -

สุดท้ายเราเรียงลำดับส่วนที่เหลือของอาร์เรย์โดยใช้ช่วงของค่า 1 การเรียงเชลล์ใช้การเรียงลำดับการแทรกเพื่อจัดเรียงอาร์เรย์

ต่อไปนี้เป็นภาพทีละขั้นตอน -

เราเห็นว่ามันต้องใช้เพียงสี่ swaps ในการจัดเรียงอาร์เรย์ที่เหลือ

อัลกอริทึม

ต่อไปนี้เป็นอัลกอริทึมสำหรับการจัดเรียงเชลล์

Step 1 − Initialize the value of h
Step 2 − Divide the list into smaller sub-list of equal interval h
Step 3 − Sort these sub-lists using insertion sort
Step 3 − Repeat until complete list is sorted

รหัสเทียม

ต่อไปนี้คือ pseudocode สำหรับการจัดเรียงเชลล์

procedure shellSort()
   A : array of items 
	
   /* calculate interval*/
   while interval < A.length /3 do:
      interval = interval * 3 + 1	    
   end while
   
   while interval > 0 do:

      for outer = interval; outer < A.length; outer ++ do:

      /* select value to be inserted */
      valueToInsert = A[outer]
      inner = outer;

         /*shift element towards right*/
         while inner > interval -1 && A[inner - interval] >= valueToInsert do:
            A[inner] = A[inner - interval]
            inner = inner - interval
         end while

      /* insert the number at hole position */
      A[inner] = valueToInsert

      end for

   /* calculate interval*/
   interval = (interval -1) /3;	  

   end while
   
end procedure

หากต้องการทราบข้อมูลเกี่ยวกับการดำเนินการจัดเรียงเปลือกในการเขียนโปรแกรมภาษา C โปรดคลิกที่นี่