如何使插入排序与日期一起工作?

huangapple go评论85阅读模式
英文:

How to get insertion sort to work with dates?

问题

对于一个关于算法的作业,我正在尝试使用插入排序对一个节点内存地址的数组进行排序。它似乎部分工作了。

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
}
英文:

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 &lt; n; i++ {
		data := arr[i]
		last := i
		dataDate, _:= time.Parse(&quot;02/01/2006&quot;, data.date)
		lastDate, _:= time.Parse(&quot;02/01/2006&quot;, arr[last-1].date)
		for (last&gt;0) &amp;&amp; (lastDate.After(dataDate)) {
			arr[last] = arr[last-1]
			last--
		}
		arr[last] = data
	}
	return arr
}

答案1

得分: 1

在大多数情况下,无论是哪种语言,除非你有一个特定的用例,需要一个特定的实现来提高性能(时间/空间方面),否则你不需要自己编写排序算法。

Go标准库中包含一个sort.Slice函数,可以帮助你对任意切片进行排序。它在内部实现了快速排序

你的代码片段可以重写如下:

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
}

为了节省CPU周期,你还可以将time.Parse的输出缓存到一个map[*bookingInfoNode]time.Time映射中,这样你只需要解析每个日期字符串一次。你也可以在排序之前预先解析它们。

英文:

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(&quot;02/01/2006&quot;, arr[i].date)
        b, _ := time.Parse(&quot;02/01/2006&quot;, 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.

答案2

得分: 0

经过一些调试,我意识到我的lastDate变量在内部for循环的每次迭代中没有更新。所以我将它放在了内部for循环的条件语句中,并创建了一个包装函数来解决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
}
英文:

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 &lt; n; i++ {
		data := arr[i]
		last := i
		dataDate, _ := time.Parse(timeFormat, data.date)
		for (last &gt; 0) &amp;&amp; (getTimeFromParse(time.Parse(timeFormat, arr[last-1].date)).After(dataDate)) {
			arr[last] = arr[last-1]
			last--
		}

		arr[last] = data
	}
	return arr
}

huangapple
  • 本文由 发表于 2022年4月19日 19:11:38
  • 转载请务必保留本文链接:https://go.coder-hub.com/71923999.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定