Beranda > Delphi > How to perform a Shell Sort

How to perform a Shell Sort

Shell Sort is really just an extension of Insertion Sort, with two observations in mind:

  • Insertion Sort is efficient if the input is “almost sorted”.
  • Insertion Sort is inefficient, on average, because it moves values just one position at a time.

Shell Sort is similar to Insertion Sort, but it works by taking “bigger steps” as it rearranges values, gradually decreasing the step size down towards one. In the end, Shell Sort performs a regular Insertion Sort but by then, the array of data is guaranteed to be “almost sorted”.

Consider a small value that is initially stored in the wrong end of the array. Using Insertion Sort, it will take roughly N comparisons and exchanges to move this value all the way to the other end of the array. With Shell Sort, we’ll first move values using giant step sizes, so a small value will move a long way towards it’s final position, with just a few comparisons and exchanges.

procedure SortShell(var aSort: array of Word);
  iI, iJ, iK,
  iSize: Integer;
  wTemp: Word;
  iSize := High(A);
  iK := iSize shr 1;
  while iK > 0 do begin
    for iI := 0 to iSize - iK do begin
      iJ := iI;
      while (iJ >= 0) and (aSort[iJ] > aSort[iJ + iK]) do begin
        wTemp := a[iJ];
        aSort[iJ] := aSort[j + iK];
        aSort[iJ + iK] := wTemp;
        if j > iK then
          Dec(iJ, iK)
          iJ := 0
    iK := iK shr 1;
  1. Februari 18, 2013 pukul 9:10 am

    “How to perform a Shell Sort ##ats76id##” was in fact
    a remarkable posting, can not wait to read through more of ur postings.

    Time to waste several time on the web haha.
    I appreciate it ,Teddy

  1. No trackbacks yet.

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:


You are commenting using your account. Logout /  Ubah )

Foto Google+

You are commenting using your Google+ account. Logout /  Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout /  Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout /  Ubah )


Connecting to %s

%d blogger menyukai ini: