Gnomeソートはクイックソートより高速ですか？

Question

ソートアルゴリズムを掘り下げ、バブル、セレクション、グノー、挿入、マージ、クイックソートなどをPythonで実装しました。しかし、私がそれらを実行し、時代を比較したとき、O（n^2）であるグノームのソートは、O（nlogn）が信じているクイックソートよりも速かった。 質問：誰かが私のgnomeソートアルゴリズムが私のクイックマージソートアルゴリズムとそれを最適化する方法より速い理由を説明して、効率の低いアルゴリズムよりも速くソートできるようにすることはできますか？ありがとうございます。 （のPSは、あなたがソートここのGNOME聞いた場合Wikipedia Gnome Sort Algorithm役立つリンクです）

# Sorting lib 
# author: Aniekan Umoren 
# course: LEAP EngTech 
# date started: 2016-08-09 
# last modified: 2016-08-16 

import time 
from random import randrange 

def bubble_sort(arr): 
    k = 0 
    n = len(arr) 
    for numSweeps in range(n-1): 
     for i in range(n-k-1): 
      if arr[i] > arr[i+1]: 
       temp = arr[i] 
       arr[i] = arr[i+1] 
       arr[i+1] = temp 
     k += 1 
    return arr 

def selection_sort(arr): 
    n = len(arr) 
    k = 0 
    for numSweeps in range(n-1): 
     minimum = arr[k] 
     for i in range(k,n): 
      if arr[i] < minimum: 
       temp = arr[k] 
       arr[k] = arr[i] 
       arr[i] = temp 
       minimum = arr[k] 
     k += 1 
    return arr 

def gnome_sort(arr): 
    pos = 0 
    while pos < len(arr): 
     if pos == 0 or arr[pos] >= arr[pos-1]: 
      pos += 1 
     else: 
      temp = arr[pos] 
      arr[pos] = arr[pos-1] 
      arr[pos-1] = temp 
      pos -= 1 
    return arr 

def insertion_sort(arr): 
    for i in range(len(arr)): 
     x = arr[i] 
     j = i -1 
     while j >= 0 and arr[j] > x: 
      arr[j+1] = arr[j] 
      j -= 1 
     arr[j+1] = x 
    return arr 

def merge(arr1,arr2): 
    arr3 = [] 
    size1 = len(arr1); size2 = len(arr2) 
    i1 = 0; i2 = 0 
    while i1 < size1 or i2 < size2: #both list aren't empty 
     if i1 == size1: 
      arr3.append(arr2[i2]) 
      i2 += 1 
     elif i2 == size2: 
      arr3.append(arr1[i1]) 
      i1 += 1 
     elif arr1[i1] <= arr2[i2]: 
      arr3.append(arr1[i1]) 
      i1 += 1 
     elif arr2[i2] < arr1[i1]: 
      arr3.append(arr2[i2]) 
      i2 += 1 
    return arr3 

def merge_sort(Arr, start, end): 
    if start < end: 
     # size = (start + end + 1) 
     mid = (start+end)//2 
     arr1 = merge_sort(Arr,start, mid) 
     arr2 = merge_sort(Arr, mid+1, end) 
     Arr[start:end+1] = merge(arr1, arr2) 
    return Arr[start:end+1] 

def partition(Arr, start, end): 
    rand = start + randrange(end-start) 
    temp = Arr[start] 
    Arr[start] = Arr[rand] 
    Arr[rand] = temp 
    i = start + 1 
    for j in range(start+1, end+1): 
     if Arr[j] < Arr[start]: 
      temp = Arr[i] 
      Arr[i] = Arr[j] 
      Arr[j] = temp 
      i += 1 
    temp = Arr[start] 
    Arr[start] = Arr[i-1] 
    Arr[i-1] = temp 
    return (Arr,i-1) 

def quick_sort(Arr, start, end): 
    if start < end: 
     part_result = partition(Arr, start, end) 
     Arr = part_result[0] 
     piv_pos = part_result[1] 
     quick_sort(Arr, start, piv_pos-1) 
     quick_sort(Arr, piv_pos+1, end) 
    if end == len(Arr)-1: 
     return Arr 


def main(): 
    start_time = time.time() 
    li1 = [3, 1234, 123, 214, 21, 124, 125, 213, 
      34, 354, 2345,62, 34, 623, 34, 34, 53465, 
      346, 346434, 537373, 5347,73, 234, 62, 36, 
      27, 247, 4742, 47472, 24, 742, 57, 24, 7245, 24] 
    li2 = [3, 21, 24, 24, 27, 34, 34, 34, 34, 36, 
      57, 62, 62, 73, 123, 124, 125, 213, 214, 
      234, 247, 346, 354, 623, 724, 742, 1234, 
      2345, 4742, 5347, 7245, 47472, 53465, 346434, 537373] 
    li3 = sorted(li2, reverse = True) 
    li4 = [3,5,26,42,2,6] 

    for i in range(10000): 
     result = bubble_sort(li1) 
    print("BUBBLE SORT: %s seconds" % (time.time() - start_time)) 

    start_time = time.time() 
    for i in range(10000): 
     result = gnome_sort(li1) 
    print("GNOME SORT: %s seconds" % (time.time() - start_time)) # why is gnome sort sooo fast if it has a O(n**2) 

    start_time = time.time() 
    for i in range(10000): 
     result = selection_sort(li1) 
    print("SELECTION SORT: %s seconds" % (time.time() - start_time)) 

    start_time = time.time() 
    for i in range(10000): 
     result = insertion_sort(li1) 
    print("INSERTION SORT: %s seconds" % (time.time() - start_time)) 

    size = len(li1) 
    start_time = time.time() 
    for i in range(10000): 
     result = merge_sort(li1, 0, size-1) 
    print("MERGE SORT: %s seconds" % (time.time() - start_time)) 

    size = len(li1) 
    start_time = time.time() 
    for i in range(10000): 
     result = quick_sort(li1, 0, size-1) 
    print("QUICK SORT: %s seconds" % (time.time() - start_time)) 

    start_time = time.time() 
    for i in range(10000): 
     result = sorted(li1) 
    print("TIM SORT: %s seconds" % (time.time() - start_time)) 

main() 

Answer 1

あなたソートは、すべての代わりに新しいリストを返すの入力を変異するので、最初の並べ替えた後、入力がソートされ、ソートされたままです。 Gnomeソートはすでにソートされた入力ではO（n）です。