How to get insertion sort to work with dates?-CodePudding

For an assignment on algorithms, I'm trying to sort an array of node memory addresses using insertion sort. It seems to partially work?

type bookingInfoNode struct {
    car         string
    date        string
    bookingTime int
    userName    string
    pickUp      string
    dropOff     string
    contactInfo int
    remarks     string
    bookingId   string
    prev        *bookingInfoNode
    next        *bookingInfoNode
}

func sortBookingsByDate(arr []*bookingInfoNode, n int) []*bookingInfoNode {
    for i := 1; i < n; i   {
        data := arr[i]
        last := i
        dataDate, _:= time.Parse("02/01/2006", data.date)
        lastDate, _:= time.Parse("02/01/2006", arr[last-1].date)
        for (last>0) && (lastDate.After(dataDate)) {
            arr[last] = arr[last-1]
            last--
        }
        arr[last] = data
    }
    return arr
}

CodePudding user response：

In most cases, and in most languages, you don't have to code sorting algorithms yourself unless you have a use case where a specific implementation might bring you better performances (time/space-wise)

The Go standard library contains a sort.Slice function to help you sort arbitrary slices. It implements quicksort under the hood.

Your code snippet could then be rewritten as such:

func sortBookingsByDate(arr []*bookingInfoNode) []*bookingInfoNode {
    sort.Slice(arr, func(i, j int) bool {
        a, _ := time.Parse("02/01/2006", arr[i].date)
        b, _ := time.Parse("02/01/2006", arr[j].date)
        return a.Before(b)
    }
    return arr
}

To save CPU cycles, you could also cache the time.Parse outputs into a map[*bookingInfoNode]time.Time map. So you only ever parse each date string once. You could also pre-parse it ahead of the sort.

CodePudding user response：

After some debugging, I realized that my lastDate variable was not updating with every iteration of the inner for loop. So I placed it as one of my conditionals in my inner for loop and created a wrapper function to get rid of the error from time.Parse

func getTimeFromParse(d time.Time, _ error) time.Time {
    return d
}

func sortBookingsByDate(arr []*bookingInfoNode, n int) []*bookingInfoNode {
    for i := 1; i < n; i   {
        data := arr[i]
        last := i
        dataDate, _ := time.Parse(timeFormat, data.date)
        for (last > 0) && (getTimeFromParse(time.Parse(timeFormat, arr[last-1].date)).After(dataDate)) {
            arr[last] = arr[last-1]
            last--
        }

        arr[last] = data
    }
    return arr
}