Skip to content

Instantly share code, notes, and snippets.

@lironsade

lironsade/algo.py

Last active January 6, 2019 10:53
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save lironsade/4e20686c2950826324f70b26b576e4fe to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save lironsade/4e20686c2950826324f70b26b576e4fe to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. lironsade revised this gist Jan 6, 2019. 1 changed file with 34 additions and 1 deletion.
    35 changes: 34 additions & 1 deletion algo.py
    View file
    Original file line number Diff line number Diff line change
    @@ -28,9 +28,42 @@ def mergeSort(A):

    return A

    def partition(A, first, last):
    pivot = A[last]

    lefti = first + 1
    righti = last

    done = False
    while not done:
    while lefti <= righti and A[lefti] <= pivot:
    lefti += 1

    while A[righti] >= pivot and righti >= lefti:
    righti -= 1

    if righti < lefti:
    done =True
    else:
    temp = A[lefti]
    A[lefti] = A[righti]
    A[righti] = temp
    temp = A[lefti]
    A[lefti] = A[righti]
    A[righti] = temp

    return righti


    def quickSortHelper(A, left, right):
    if left < right:
    ind = partition(A, left, right)

    quickSortHelper(A, left, ind - 1)
    quickSortHelper(A, i + 1, right)

    def quickSort(A):
    pass
    return quickSortHelper(A, 0, len(A) - 1)

    def BFS(G):
    pass
  2. lironsade revised this gist Jan 6, 2019. 1 changed file with 24 additions and 1 deletion.
    25 changes: 24 additions & 1 deletion algo.py
    View file
    Original file line number Diff line number Diff line change
    @@ -4,7 +4,30 @@ def mergeSort(A):
    left = mergeSort(A[:mid])
    right = mergeSort(A[mid:])

    pass
    # merge
    i = j = k = 0
    while i < len(left) and j < len(right):
    if left[i] < right[j]:
    A[k] = left[i]
    i += 1
    else:
    A[k] = right[j]
    j += 1
    k += 1

    while i < len(left):
    A[k] = left[i]
    i += 1
    k += 1


    while j < len(right):
    A[k] = right[j]
    j += 1
    k += 1

    return A


    def quickSort(A):
    pass
  3. lironsade revised this gist Jan 5, 2019. 1 changed file with 5 additions and 0 deletions.
    5 changes: 5 additions & 0 deletions algo.py
    View file
    Original file line number Diff line number Diff line change
    @@ -1,4 +1,9 @@
    def mergeSort(A):
    mid = len(A) // 2
    if len(A) > 1:
    left = mergeSort(A[:mid])
    right = mergeSort(A[mid:])

    pass

    def quickSort(A):
  4. lironsade created this gist Jan 5, 2019.
    14 changes: 14 additions & 0 deletions algo.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,14 @@
    def mergeSort(A):
    pass

    def quickSort(A):
    pass

    def BFS(G):
    pass

    def DFS(G):
    pass

    def binarySearch(A, x):
    pass